Cover Image

A Polynomial Decision for 3-SAT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Weiss, Angela
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Polynomial time Algorithm for 3SAT
by: Du, Lizhi
Published: (2010)

New Algorithms for #2-SAT and #3-SAT
by: Peng, Junqiang, et al.
Published: (2025)

Maximum And- vs. Even-SAT
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

An Improved Algorithm for Sparse Instances of SAT
by: Jain, Sanjay, et al.
Published: (2024)

Computing diverse pair of solutions for tractable SAT
by: Gima, Tatsuya, et al.
Published: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
by: Jain, Sanjay, et al.
Published: (2026)

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

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

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

On the Parameterized Complexity of Diverse SAT
by: Misra, Neeldhara, et al.
Published: (2024)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
by: Manurangsi, Pasin
Published: (2024)

Hypergraph Unreliability in Quasi-Polynomial Time
by: Cen, Ruoxu, et al.
Published: (2024)

Quantum Graph-State Synthesis with SAT
by: Brand, Sebastiaan, et al.
Published: (2023)

Further Explanations on "SAT Requires Exhaustive Search"
by: Dong, Qingxiu, et al.
Published: (2024)

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
by: Huang, Chien-Chung, et al.
Published: (2026)

Counting and Sampling Labeled Chordal Graphs in Polynomial Time
by: Hebert-Johnson, Ursula, et al.
Published: (2023)

Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
by: Hébert-Johnson, Úrsula, et al.
Published: (2025)

A Polynomial-time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs
by: Cenciarelli, Pietro, et al.
Published: (2016)

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
by: Dadush, Daniel, et al.
Published: (2025)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
by: Nezhad, Sina Bagheri, et al.
Published: (2025)

Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion
by: Houari-Durand, Séhane Bel, et al.
Published: (2025)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
by: Haeupler, Bernhard, et al.
Published: (2026)

Counting random $k$-SAT near the satisfiability threshold
by: Chen, Zongchen, et al.
Published: (2024)

Random local access for sampling k-SAT solutions
by: Dong, Dingding, et al.
Published: (2024)

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

Polynomial Property Testing
by: Gishboliner, Lior, et al.
Published: (2025)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
by: Chen, Kuowen, et al.
Published: (2025)

A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity
by: Tayal, Mumuksh
Published: (2025)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
by: Jourdan, Ben, et al.
Published: (2024)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
by: Bampis, Evripidis, et al.
Published: (2025)

A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor
by: Groenland, Carla, et al.
Published: (2024)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)

Assessing fault-tolerant quantum advantage for $k$-SAT with structure
by: Brehm, Martijn, et al.
Published: (2024)

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

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Algorithms Transcending the SAT-Symmetry Interface
by: Anders, Markus, et al.
Published: (2023)

An algorithmic Polynomial Freiman-Ruzsa theorem
by: Castro-Silva, Davi, et al.
Published: (2026)