Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates

zbMATH Open1289.68049MaRDI QIDQ2850118FDOQ2850118

Authors: V. O. Mykhajlyuk 

Publication date: 26 September 2013

Published in: Dopovidi Natsional'noï Akademiï Nauk Ukraïny. Matematyka, Pryrodoznavstvo, Tekhnichni Nauky (Search for Journal in Brave)

Recommendations

• Reoptimization of constraint satisfaction problems with approximation resistant predicates
• A threshold for a polynomial solution of \#2SAT
• Re-optimization of constraint satisfaction problems with predicates of arity two
• On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy
• scientific article; zbMATH DE number 1759450
• A perspective on certain polynomial-time solvable classes of satisfiability
• Upper and lower bounds on the complexity of generalised resolution and generalised constraint satisfaction problems
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Upper bounds on the satisfiability threshold
• Quantified constraint satisfaction and the polynomially generated powers property

zbMATH Keywords

approximation algorithmthreshold reoptimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (6)

• Approximation to the reoptimization optimal sublinear algorithms of bounded-degree problems of a general feasibility
• Re-optimization of constraint satisfaction problems with predicates of arity two
• On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field
• Recognition of tractable satisfiability problems through balanced polynomial representations
• A threshold for a polynomial solution of \#2SAT
• Reoptimization of constraint satisfaction problems with approximation resistant predicates

This page was built for publication: Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates

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