Image de couverture de livre

Further Explanations on "SAT Requires Exhaustive Search"

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Dong, Qingxiu, Zhou, Guangyan, Xu, Ke
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

SAT Requires Exhaustive Search
par: Xu, Ke, et autres
Publié: (2023)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Solution independence and self-referential instances
par: Zhou, Guangyan, et autres
Publié: (2026)

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

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

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

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

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
par: Scheder, Dominik, et autres
Publié: (2025)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2025)

Complexity of Local Search for Euclidean Clustering Problems
par: Manthey, Bodo, et autres
Publié: (2023)

The Query Complexity of Local Search and Brouwer in Rounds
par: Brânzei, Simina, et autres
Publié: (2020)

The Query Complexity of Local Search in Rounds on General Graphs
par: Brânzei, Simina, et autres
Publié: (2026)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
par: Jansen, Bart M. P., et autres
Publié: (2026)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
par: Balzereit, Kaja, et autres
Publié: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
par: Grüttemeier, Niels, et autres
Publié: (2025)

More Asymmetry Yields Faster Matrix Multiplication
par: Alman, Josh, et autres
Publié: (2024)

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

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
par: Kothari, Pravesh K., et autres
Publié: (2025)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
par: Bedert, Benjamin, et autres
Publié: (2025)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
par: Sarriguren, Alfredo Goñi
Publié: (2024)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
par: Kızıldağ, Eren C.
Publié: (2023)

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
par: Epasto, Alessandro, et autres
Publié: (2026)

Quantum Search with In-Place Queries
par: Holman, Blake, et autres
Publié: (2025)

Can You Link Up With Treewidth?
par: Curticapean, Radu, et autres
Publié: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
par: Wang, Yichuan
Publié: (2024)

Simple approximation algorithms for Polyamorous Scheduling
par: Biktairov, Yuriy, et autres
Publié: (2024)

Size Minimization For Multi-Output AND-Functions
par: Armbruster, Susanne
Publié: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
par: Stoian, Mihail
Publié: (2024)

Cluster Editing on Cographs and Related Classes
par: Lafond, Manuel, et autres
Publié: (2024)

Improved Hardness-of-Approximation for Token Swapping
par: Hiken, Sam, et autres
Publié: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
par: Xun, Zhiyang, et autres
Publié: (2024)

On the complexity and approximability of Bounded access Lempel Ziv coding
par: Cicalese, Ferdinando, et autres
Publié: (2024)

Parameterized Vertex Integrity Revisited
par: Hanaka, Tesshu, et autres
Publié: (2024)

On approximability of the Permanent of PSD matrices
par: Ebrahimnejad, Farzam, et autres
Publié: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
par: Sato, Atsuki, et autres
Publié: (2024)

Randomized query composition and product distributions
par: Sanyal, Swagato
Publié: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
par: Heeger, Klaus, et autres
Publié: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
par: Stoian, Mihail
Publié: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
par: Kuschner, Jordan, et autres
Publié: (2024)