Generalizations of Opt P to the polynomial hierarchy
From MaRDI portal
Publication:1193867
DOI10.1016/0304-3975(92)90073-OzbMath0769.68031MaRDI QIDQ1193867
Publication date: 27 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, The operators min and max on the polynomial hierarchy, Complexity of counting the optimal solutions, The complexity of optimization problems, Taking into account ``who said what in abstract argumentation: complexity results, Complexity of Counting the Optimal Solutions, Counting Complexity of Minimal Cardinality and Minimal Weight Abduction, Optimal satisfiability for propositional calculi and constraint satisfaction problems., The Complexity Landscape of Outcome Determination in Judgment Aggregation, Unnamed Item, Counting complexity of propositional abduction, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- The complexity of facets (and some facets of complexity)
- Games against nature
- NP is as easy as detecting unique solutions
- The complexity of combinatorial problems with succinct input representation
- The complexity of optimization problems
- How easy is local search?
- The polynomial-time hierarchy
- On the complexity of some two-person perfect-information games
- Simple Local Search Problems that are Hard to Solve
- Alternation
- An Efficient Heuristic Procedure for Partitioning Graphs
