:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Darmann, Andreas, Döcker, Janosch, Dorn, Britta
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2412.03395
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the existence of funneled orientations for classes of rooted phylogenetic networks
by: Döcker, Janosch, et al.
Published: (2024)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
by: Krokhin, Andrei, et al.
Published: (2025)

Local Enumeration: The Not-All-Equal Case
by: Gurumukhani, Mohit, et al.
Published: (2025)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
by: Durand, Martin
Published: (2026)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
by: Ron-Zewi, Noga, et al.
Published: (2024)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)

Finding hardness reductions automatically using SAT solvers
by: Bergold, Helena, et al.
Published: (2024)

An Intrinsic Barrier for Resolving P = NP (2-SAT as Flat, 3-SAT as High-Dimensional Void-Rich)
by: Alasli, M.
Published: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

A Reply to "On Salum's Algorithm for X3SAT"
by: Salum, Latif
Published: (2021)

Linear Planar 3-SAT and Its Applications in Planning
by: Desbois, Victorien, et al.
Published: (2025)

On the hardness of recognizing graphs of small mim-width and its variants
by: la Tour, Max Dupré, et al.
Published: (2025)

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
by: Krebs, Andreas, et al.
Published: (2025)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
by: He, Yumeng, et al.
Published: (2024)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
by: DeJesse, Nicholas, et al.
Published: (2025)

The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

Geometric Interpretation of 3-SAT and Phase Transition
by: Gillet, Frederic
Published: (2025)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
by: Laakkonen, Tuomas, et al.
Published: (2022)

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

On the Mysteries of MAX NAE-SAT
by: Brakensiek, Joshua, et al.
Published: (2020)

Quantum k-SAT Related Hypergraph Problems
by: Kremer, Simon-Luca, et al.
Published: (2025)

Injective hardness condition for PCSPs
by: Banakh, Demian, et al.
Published: (2024)

If VNP is hard, then so are equations for it
by: Kumar, Mrinal, et al.
Published: (2020)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

Exact Quantum Circuit Optimization is co-NQP-hard
by: Kjelstrøm, Adam Husted, et al.
Published: (2025)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
by: Han, Zicheng, et al.
Published: (2026)

Ruling Out Low-rank Matrix Multiplication Tensor Decompositions with Symmetries via SAT
by: Yang, Jason
Published: (2024)

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses
by: Caragiannis, Ioannis, et al.
Published: (2024)

Coordinating "7 Billion Humans" is hard
by: Panconesi, Alessandro, et al.
Published: (2024)

On the hardness of finding normal surfaces
by: Burton, Benjamin A., et al.
Published: (2019)

Further Explanations on "SAT Requires Exhaustive Search"
by: Dong, Qingxiu, et al.
Published: (2024)

A Note On The Natural Range Of Unambiguous-SAT
by: Pay, Tayfun
Published: (2023)

BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs
by: Baudin, Alexis, et al.
Published: (2024)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
by: Romão, Leonardo Gasparini, et al.
Published: (2025)

SAT, Gadgets, Max2XOR, and Quantum Annealers
by: Ansótegui, Carlos, et al.
Published: (2024)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
by: Cardoso, Ricardo Rivera, et al.
Published: (2025)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
by: Austrin, Per, et al.
Published: (2024)