Copertina

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	DeJesse, Nicholas, Lyudovyk, Spencer, Pai, Dhruv
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

A Polynomial Time Algorithm for 3SAT
di: Quigley, Robert
Pubblicazione: (2024)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
di: Le, Tran Duy Anh, et al.
Pubblicazione: (2024)

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

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

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
di: Kosoy, Vanessa, et al.
Pubblicazione: (2016)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

Extractors for Polynomial Sources over $\mathbb{F}_2$
di: Chattopadhyay, Eshan, et al.
Pubblicazione: (2023)

A Critique of Deng's "P=NP"
di: Humphreys, Isabel, et al.
Pubblicazione: (2025)

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

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
di: Gibor, Daniel
Pubblicazione: (2025)

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

Low-Degree Polynomials Are Good Extractors
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
di: Bedert, Benjamin, et al.
Pubblicazione: (2025)

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

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

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

One-Way Functions and Polynomial Time Dimension
di: Nandakumar, Satyadev, et al.
Pubblicazione: (2024)

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

Polynomial-Time PIT from (Almost) Necessary Assumptions
di: Andrews, Robert, et al.
Pubblicazione: (2025)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
di: Wang, Cancan, et al.
Pubblicazione: (2024)

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
di: Wu, Mingyou
Pubblicazione: (2024)

Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
di: Zhan, Yongjian
Pubblicazione: (2026)

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

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
di: Chia, Nai-Hui, et al.
Pubblicazione: (2024)

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

Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition
di: Hazra, Rishi, et al.
Pubblicazione: (2025)

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

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
di: Shao, Shuai, et al.
Pubblicazione: (2023)

A Schematic Definition of Quantum Polynomial Time Computability
di: Yamakami, Tomoyuki
Pubblicazione: (2018)

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

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

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

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

Testing Isomorphism of Graphs in Polynomial Time
di: Xue, Rui
Pubblicazione: (2023)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
di: Amireddy, Prashanth, et al.
Pubblicazione: (2025)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
di: Yao, Penghui, et al.
Pubblicazione: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
di: Michno, Katzper
Pubblicazione: (2025)