Image de couverture de livre

A Graphical #SAT Algorithm for Formulae with Small Clause Density

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Laakkonen, Tuomas, Meichanetzidis, Konstantinos, van de Wetering, John
Format:	Preprint
Publié:	2022
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Quantum Algorithms for Compositional Text Processing
par: Laakkonen, Tuomas, et autres
Publié: (2024)

Formal Framework for Quantum Advantage
par: Buhrman, Harry, et autres
Publié: (2025)

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

Optimising quantum circuits is generally hard
par: van de Wetering, John, et autres
Publié: (2023)

Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
par: González-Castillo, Samuel, et autres
Publié: (2026)

A Reply to "On Salum's Algorithm for X3SAT"
par: Salum, Latif
Publié: (2021)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
par: DeJesse, Nicholas, et autres
Publié: (2025)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
par: He, Yumeng, et autres
Publié: (2024)

A Polynomial Time Algorithm for 3SAT
par: Quigley, Robert
Publié: (2024)

Testing for Renamability to Classes of Clause Sets
par: Brandl, Albert, et autres
Publié: (2025)

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

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
par: Buhrman, Harry, et autres
Publié: (2025)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
par: Riazanov, Artur, et autres
Publié: (2025)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
par: Austrin, Per, et autres
Publié: (2024)

Linear Planar 3-SAT and Its Applications in Planning
par: Desbois, Victorien, et autres
Publié: (2025)

An even simpler hard variant of Not-All-Equal 3-SAT
par: Darmann, Andreas, et autres
Publié: (2024)

Lift-and-Project Integrality Gaps for Santa Claus
par: Bamas, Etienne
Publié: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
par: Han, Zicheng, et autres
Publié: (2026)

On the Complexity of Hazard-Free Formulas
par: Arazi, Leah London, et autres
Publié: (2024)

Approximately counting maximal independent set is equivalent to #SAT
par: Zhang, Hao, et autres
Publié: (2024)

Hard CNF Instances for Ideal Proof Systems
par: Hakoniemi, Tuomas, et autres
Publié: (2026)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
par: Krokhin, Andrei, et autres
Publié: (2025)

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

IPS Lower Bounds for Formulas and Sum of ROABPs
par: Chatterjee, Prerona, et autres
Publié: (2025)

On the Mysteries of MAX NAE-SAT
par: Brakensiek, Joshua, et autres
Publié: (2020)

Quantum k-SAT Related Hypergraph Problems
par: Kremer, Simon-Luca, et autres
Publié: (2025)

FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming
par: Beniamini, Gal, et autres
Publié: (2025)

A Note On The Natural Range Of Unambiguous-SAT
par: Pay, Tayfun
Publié: (2023)

Graphical Tests of Causality
par: Baumeler, Ämin, et autres
Publié: (2025)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
par: Komarath, Balagopal, et autres
Publié: (2025)

Circuits and Formulas for Datalog over Semirings
par: Fan, Austen Z., et autres
Publié: (2025)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
par: Yamakami, Tomoyuki
Publié: (2017)

Geometric Interpretation of 3-SAT and Phase Transition
par: Gillet, Frederic
Publié: (2025)

Further Explanations on "SAT Requires Exhaustive Search"
par: Dong, Qingxiu, et autres
Publié: (2024)

Hard Clique Formulas for Resolution
par: Atserias, Albert
Publié: (2026)

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

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
par: Krebs, Andreas, et autres
Publié: (2025)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
par: Cardoso, Ricardo Rivera, et autres
Publié: (2025)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
par: Li, Zhengyu, et autres
Publié: (2023)

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
par: Schreiber, Franz J., et autres
Publié: (2025)