A simplified NP-complete MAXSAT problem

DOI10.1016/S0020-0190(97)00223-8MaRDI QIDQ293164zbMATH OpenOpenAlexFDO

Authors Venkatesh Raman, S. Srinivasa Rao, B. 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

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

Recommendations

• A simplified NP-complete satisfiability problem
• Exact algorithms for MAX-SAT
• A new upper bound for \(( n , 3)\)-MAX-SAT
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete

Cites work

• A simplified NP-complete satisfiability problem
• scientific article; zbMATH DE number 515744 (Why is no real title available?)
• On the complexity of the maximum satisfiability problem for Horn formulas
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Solving satisfiability in less than \(2^ n\) steps
• Some simplified NP-complete graph problems
• The Euclidean traveling salesman problem is NP-complete
• The Minimum Satisfiability Problem
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(28)

• A polynomial-time algorithm for reducing the number of variables in MAX SAT problem
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• A new upper bound for \(( n , 3)\)-MAX-SAT
• Max NP-completeness made easy
• An improved algorithm for the (n, 3)-MaxSAT problem: asking branchings to satisfy the clauses
• Learning hierarchical probabilistic logic programs
• A refined branching algorithm for the maximum satisfiability problem
• Directed molecular evolution by machine learning and the influence of nonlinear interactions
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment
• 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
• Network design with a discrete set of traffic matrices
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Improved \textsc{MaxSAT} algorithms for instances of degree 3
• Complexity of partial satisfaction. II.
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• About a surprising computer program of Matthias Müller
• Popular spanning trees
• On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
• On star partition of split graphs
• The maximum 3-star packing problem in claw-free cubic graphs
• From MAXCUT to MAXNAESAT: elegant proofs and algorithmic advances
• Fast exact algorithms for the SAT problem with bounded occurrences of variables
• A simplified NP-complete satisfiability problem
• Optimal 2-constraint satisfaction via sum-product algorithms
• The inequality-satisfiability problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293164)