Cover Image

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Krokhin, Andrei, Vagnozzi, Danny
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
by: Nakajima, Tamio-Vesa, et al.
Published: (2025)

Three Hardness Results for Graph Similarity Problems
by: Sun, He, et al.
Published: (2023)

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

An even simpler hard variant of Not-All-Equal 3-SAT
by: Darmann, Andreas, et al.
Published: (2024)

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

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

NP-hardness of SVP in Euclidean Space
by: Wan, Daqing
Published: (2026)

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

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
by: Baraskar, Omkar, et al.
Published: (2024)

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

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

Prove Symbolic Regression is NP-hard by Symbol Graph
by: Song, Jinglu, et al.
Published: (2024)

Data Debugging is NP-hard for Classifiers Trained with SGD
by: Guo, Zizheng, et al.
Published: (2024)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
by: Martinsson, Björn
Published: (2024)

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

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

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

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

Structural Origin and the Minimal Syntax of NP-Hardness: Analysis of SAT from Syntactic Generativity and Compositional Collapse
by: Nishiyama, Yumiko
Published: (2025)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by: Heeger, Klaus, et al.
Published: (2024)

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

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

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

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

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)

P=NP
by: Deng, Zikang
Published: (2024)

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

P vs. NP
by: Uribe, Daniel
Published: (2016)

On P Versus NP
by: Gordeev, Lev
Published: (2020)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
by: Hair, Isaac M., et al.
Published: (2025)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
by: DeJesse, Nicholas, et al.
Published: (2025)

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

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