Cover Image

An Efficient Algorithm for Solving the 2-MAXSAT Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Chen, Yangjun
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
by: Digulescu, Mircea-Adrian
Published: (2026)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
by: Lichter, Moritz, et al.
Published: (2024)

P-time Algorithms for Typical #EO Problems
by: Meng, Boning, et al.
Published: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
by: Yung, Kingsley
Published: (2024)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
by: Li, Zhiyuan, et al.
Published: (2024)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
by: Lemke, Caroline, et al.
Published: (2025)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
by: Gaikwad, Ajinkya, et al.
Published: (2025)

Space Efficient Algorithms for Parameterised Problems
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
by: Yi, Yongming
Published: (2026)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

Solving Four Open Problems about Core Stability in Altruistic Hedonic Games
by: Rothe, Jörg, et al.
Published: (2025)

The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)

An Efficient Quantum Factoring Algorithm
by: Regev, Oded
Published: (2023)

Efficient Algorithms for Quantum Hashing
by: Zinnatullin, Ilnar, et al.
Published: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving
by: AbdElhameed, Marwan, et al.
Published: (2024)

Solving The Travelling Salesman Problem Using A Single Qubit
by: Goswami, Kapil, et al.
Published: (2024)

Virtual Qudits for Simon's Problem: Dimension-Lifted Algorithms on Qubit Hardware
by: Semre, Abed, et al.
Published: (2025)

Review of Automaton Learning Algorithms with Polynomial Complexity -- Completely Solved Examples
by: Haneef, Farah
Published: (2024)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
by: Yamakami, Tomoyuki
Published: (2017)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
by: MIT Hardness Group, et al.
Published: (2024)

On Computability of Computable Problems
by: Khaliq, Asad
Published: (2023)

The Stochastic Arrival Problem
by: Webster, Thomas
Published: (2022)

The Greedy Coin Change Problem
by: Gupta, Shreya, et al.
Published: (2024)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

Continuous Defensive Domination Problems
by: Grüne, Christoph, et al.
Published: (2026)

Solving 4-Block Integer Linear Programs Faster Using Affine Decompositions of the Right-Hand Sides
by: Lassota, Alexandra, et al.
Published: (2026)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

Reductions Between Code Equivalence Problems
by: Cheraghchi, Mahdi, et al.
Published: (2025)

Total Search Problems in $\mathsf{ZPP}$
by: Fleming, Noah, et al.
Published: (2025)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

On the Exact Matching Problem in Dense Graphs
by: Maalouly, Nicolas El, et al.
Published: (2024)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
by: Li, Chenyang, et al.
Published: (2025)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)

The Line Traveling Salesman and Repairman Problem with Collaboration
by: Golak, Julian, et al.
Published: (2025)

Maximum Matching and Related Problems in Catalytic Logspace
by: Chakraborty, Srijan, et al.
Published: (2026)