Optimization problems and the polynomial hierarchy
From MaRDI portal
Publication:1152218
DOI10.1016/0304-3975(81)90082-7zbMATH Open0459.68016OpenAlexW1972528014MaRDI QIDQ1152218FDOQ1152218
Authors: E. W. jun. Leggett, Daniel J. Moore 
Publication date: 1981
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(81)90082-7
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- The complexity of theorem-proving procedures
- Some simplified NP-complete graph problems
- P-Complete Approximation Problems
- Title not available (Why is that?)
- The polynomial-time hierarchy
- Computationally Related Problems
- A comparison of polynomial time reducibilities
- Complete sets and the polynomial-time hierarchy
- Polynomial Time Enumeration Reducibility
- A second step toward the polynomial hierarchy
- Translational lemmas, polynomial time, and \((\log n)^j\)-space
Cited In (9)
- Geometric optimization and \(D^ P\)-completeness
- The difference and truth-table hierarchies for NP
- On fixed-parameter tractability and approximability of NP optimization problems
- Geometric optimization and the polynomial hierarchy
- On the Stackelberg knapsack game
- The complexity of facets (and some facets of complexity)
- On a three-level competitive pricing problem with uniform and mill pricing strategies
- Comparison of metaheuristics for the bilevel facility location and mill pricing problem
- On the complexity of test case generation for NP-hard problems
This page was built for publication: Optimization problems and the polynomial hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1152218)
