Optimization problems and the polynomial hierarchy

DOI10.1016/0304-3975(81)90082-7zbMath0459.68016OpenAlexW1972528014MaRDI QIDQ1152218

Daniel J. Moore, E. W. jun. Leggett

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

zbMATH Keywords

traveling salesman problemchromatic number problemKnapsack packing problemmaximal clique problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)

Related Items

Geometric optimization and the polynomial hierarchy, Comparison of metaheuristics for the bilevel facility location and mill pricing problem, Geometric optimization and \(D^ P\)-completeness, On fixed-parameter tractability and approximability of NP optimization problems, The difference and truth-table hierarchies for NP, On the complexity of test case generation for NP-hard problems, On the Stackelberg knapsack game, On a Three-Level Competitive Pricing Problem with Uniform and Mill Pricing Strategies, The complexity of facets (and some facets of complexity)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of polynomial time reducibilities
• Translational lemmas, polynomial time, and \((\log n)^j\)-space
• Some simplified NP-complete graph problems
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• A second step toward the polynomial hierarchy
• P-Complete Approximation Problems
• Polynomial Time Enumeration Reducibility
• Reducibility among Combinatorial Problems
• Computationally Related Problems
• The complexity of theorem-proving procedures