Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
From MaRDI portal
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
Cited in
(6)- Recognition of tractable satisfiability problems through balanced polynomial representations
- Approximation to the reoptimization optimal sublinear algorithms of bounded-degree problems of a general feasibility
- A threshold for a polynomial solution of \#2SAT
- Reoptimization of constraint satisfaction problems with approximation resistant predicates
- On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field
- Re-optimization of constraint satisfaction problems with predicates of arity two
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)
