A simplified NP-complete MAXSAT problem

DOI10.1016/S0020-0190(97)00223-8zbMath1339.68122OpenAlexW2052367117MaRDI QIDQ293164

S. Srinivasa Rao, Venkatesh Raman, Bala Ravikumar

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002238?np=y

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Optimal 2-constraint satisfaction via sum-product algorithms ⋮ Improved MaxSAT Algorithms for Instances of Degree 3 ⋮ On the computational complexity of Roman\(\{2\}\)-domination in grid graphs ⋮ Directed molecular evolution by machine learning and the influence of nonlinear interactions ⋮ Gene tree reconciliation including transfers with replacement is NP-hard and FPT ⋮ Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms ⋮ Drawing (complete) binary tanglegrams ⋮ Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. ⋮ A new upper bound for \(( n , 3)\)-MAX-SAT ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Network design with a discrete set of traffic matrices ⋮ POPULAR SPANNING TREES ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses ⋮ Learning hierarchical probabilistic logic programs ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ A refined branching algorithm for the maximum satisfiability problem

Cites Work

• Unnamed Item
• A simplified NP-complete satisfiability problem
• Solving satisfiability in less than \(2^ n\) steps
• On the complexity of the maximum satisfiability problem for Horn formulas
• Some simplified NP-complete graph problems
• The Euclidean traveling salesman problem is NP-complete
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Two-Processor Scheduling with Start-Times and Deadlines
• The Minimum Satisfiability Problem

This page was built for publication: A simplified NP-complete MAXSAT problem