Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates

zbMATH Open1289.68049MaRDI QIDQ2850118

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)

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)

Related Items (2)

A threshold for a polynomial solution of \#2SAT ⋮ Recognition of tractable satisfiability problems through balanced polynomial representations

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Reoptimization of constraint satisfaction problems with approximation resistant predicates 👍 👎
• Quantified constraint satisfaction and the polynomially generated powers property 👍 👎
• 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 👍 👎
• A perspective on certain polynomial-time solvable classes of satisfiability 👍 👎
• A threshold for a polynomial solution of \#2SAT 👍 👎
• On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy 👍 👎
• Upper bounds on the satisfiability threshold 👍 👎

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)