Buchumschlag

A Polynomial Time Algorithm for 3SAT

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Quigley, Robert
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity F.2.2
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
von: Knop, Dušan, et al.
Veröffentlicht: (2017)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
von: Sarriguren, Alfredo Goñi
Veröffentlicht: (2024)

A Piecewise Approach for the Analysis of Exact Algorithms
von: Clinch, Katie, et al.
Veröffentlicht: (2024)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
von: Lagerkvist, Victor, et al.
Veröffentlicht: (2025)

Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework
von: Lee, Changryeol
Veröffentlicht: (2026)

Thin Tree Verification is coNP-Complete
von: Moayyedi, Alice
Veröffentlicht: (2025)

Fast Simulation of Cellular Automata by Self-Composition
von: Natal, Joseph, et al.
Veröffentlicht: (2024)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
von: Kiatchaipipat, Nattapol, et al.
Veröffentlicht: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
von: Fritsch, Timo, et al.
Veröffentlicht: (2026)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
von: Gupta, Chetan, et al.
Veröffentlicht: (2025)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
von: Grüne, Christoph, et al.
Veröffentlicht: (2024)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
von: Kowaluk, Miroslaw, et al.
Veröffentlicht: (2025)

Direct Sums for Parity Decision Trees
von: Besselman, Tyler, et al.
Veröffentlicht: (2024)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
von: Grüne, Christoph, et al.
Veröffentlicht: (2023)

An Algorithm for a Variation of the Shortest Common Superstring Problem
von: Gilfanov, Arthur
Veröffentlicht: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

On the Complexity of Determinations
von: Hellerstein, Joseph M.
Veröffentlicht: (2026)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
von: Bartlett, Celina Janet
Veröffentlicht: (2025)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2026)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
von: van Brügge, Jan
Veröffentlicht: (2024)

Graph Threading with Turn Costs
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)

On Minimum Maximal Distance-k Matchings
von: Kartynnik, Yury, et al.
Veröffentlicht: (2016)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
von: Dvořák, Pavel, et al.
Veröffentlicht: (2017)

Realizing temporal graphs from fastest travel times
von: Klobas, Nina, et al.
Veröffentlicht: (2023)

Proving Unsatisfiability with Hitting Formulas
von: Filmus, Yuval, et al.
Veröffentlicht: (2023)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
von: Lingas, Andrzej
Veröffentlicht: (2026)

Complexity of Firefighting on Graphs
von: Althoetmar, Julius, et al.
Veröffentlicht: (2025)

Spanning Trees Minimizing Branching Costs
von: Gargano, Luisa, et al.
Veröffentlicht: (2024)

On Small-depth Frege Proofs for PHP
von: Håstad, Johan
Veröffentlicht: (2024)

The Word Problem for Products of Symmetric Groups
von: Simon, Hans U.
Veröffentlicht: (2025)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
von: Krithika, R., et al.
Veröffentlicht: (2023)

Identity Testing for Circuits with Exponentiation Gates
von: Li, Jiatu, et al.
Veröffentlicht: (2025)

On the difficulty of order constrained pattern matching with applications to feature matching based malware detection
von: Liyanage, Adiesha, et al.
Veröffentlicht: (2025)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
von: Levin, Leonid A.
Veröffentlicht: (2022)

Towards universally optimal sorting algorithms
von: Sen, Sandeep
Veröffentlicht: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
von: Xia, Mingji
Veröffentlicht: (2026)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
von: Eua-anant, Pakapim, et al.
Veröffentlicht: (2025)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
von: Phillips, Reed
Veröffentlicht: (2026)

The Complexity of Graph Exploration Games
von: Fuchs, Janosch, et al.
Veröffentlicht: (2023)