Buchumschlag

An even simpler hard variant of Not-All-Equal 3-SAT

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Darmann, Andreas, Döcker, Janosch, Dorn, Britta
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

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

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
von: Durand, Martin
Veröffentlicht: (2026)

Local Enumeration: The Not-All-Equal Case
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2025)

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

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

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

A Reply to "On Salum's Algorithm for X3SAT"
von: Salum, Latif
Veröffentlicht: (2021)

Linear Planar 3-SAT and Its Applications in Planning
von: Desbois, Victorien, et al.
Veröffentlicht: (2025)

Finding hardness reductions automatically using SAT solvers
von: Bergold, Helena, et al.
Veröffentlicht: (2024)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

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

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

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
von: DeJesse, Nicholas, et al.
Veröffentlicht: (2025)

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
von: Krebs, Andreas, et al.
Veröffentlicht: (2025)

The 2-Attractor Problem is NP-Complete
von: Fuchs, Janosch, et al.
Veröffentlicht: (2023)

Negations are powerful even in small depth
von: Cavalar, Bruno, et al.
Veröffentlicht: (2025)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
von: Laakkonen, Tuomas, et al.
Veröffentlicht: (2022)

A Polynomial Time Algorithm for 3SAT
von: Quigley, Robert
Veröffentlicht: (2024)

Geometric Interpretation of 3-SAT and Phase Transition
von: Gillet, Frederic
Veröffentlicht: (2025)

Approximately counting maximal independent set is equivalent to #SAT
von: Zhang, Hao, et al.
Veröffentlicht: (2024)

Injective hardness condition for PCSPs
von: Banakh, Demian, et al.
Veröffentlicht: (2024)

If VNP is hard, then so are equations for it
von: Kumar, Mrinal, et al.
Veröffentlicht: (2020)

Communication Complexity is NP-hard
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Ruling Out Low-rank Matrix Multiplication Tensor Decompositions with Symmetries via SAT
von: Yang, Jason
Veröffentlicht: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
von: Han, Zicheng, et al.
Veröffentlicht: (2026)

Coordinating "7 Billion Humans" is hard
von: Panconesi, Alessandro, et al.
Veröffentlicht: (2024)

Exact Quantum Circuit Optimization is co-NQP-hard
von: Kjelstrøm, Adam Husted, et al.
Veröffentlicht: (2025)

On the Mysteries of MAX NAE-SAT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2020)

Quantum k-SAT Related Hypergraph Problems
von: Kremer, Simon-Luca, et al.
Veröffentlicht: (2025)

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

On the hardness of finding normal surfaces
von: Burton, Benjamin A., et al.
Veröffentlicht: (2019)

Partial Minimum Branching Program Size Problem is ETH-hard
von: Glinskih, Ludmila, et al.
Veröffentlicht: (2024)

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

Further Explanations on "SAT Requires Exhaustive Search"
von: Dong, Qingxiu, et al.
Veröffentlicht: (2024)

A Note On The Natural Range Of Unambiguous-SAT
von: Pay, Tayfun
Veröffentlicht: (2023)

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
von: Baraskar, Omkar, et al.
Veröffentlicht: (2024)

Man, these New York Times games are hard! A computational perspective
von: Alberti, Alessandro Giovanni, et al.
Veröffentlicht: (2025)

Sorting by pile shuffles on queue-like and stack-like piles can be hard
von: Treleaven, Kyle B.
Veröffentlicht: (2025)

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