Optimization problems and the polynomial hierarchy
type: Item
instance of: scholarly article
title: Optimization problems and the polynomial hierarchy
zbMATH Open document ID: 0459.68016
DOI: 10.1016/0304-3975(81)90082-7
author: E. W. jun. Leggett
author: Daniel J. Moore
published in: Theoretical Computer Science
publication date: 1981-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3720354
zbMATH Keywords: traveling salesman problem
zbMATH Keywords: chromatic number problem
zbMATH Keywords: maximal clique problem
zbMATH Keywords: Knapsack packing problem
MaRDI profile type: Publication
full work available at URL: 0304-3975(81)90082-7
OpenAlex ID: W1972528014
cites work: Q4091421
cites work: A second step toward the polynomial hierarchy
cites work: Translational lemmas, polynomial time, and \((\log n)^j\)-space
cites work: The complexity of theorem-proving procedures
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Reducibility among Combinatorial Problems
cites work: A comparison of polynomial time reducibilities
cites work: Q4131648
cites work: Computationally Related Problems
cites work: P-Complete Approximation Problems
cites work: Polynomial Time Enumeration Reducibility
cites work: The polynomial-time hierarchy
cites work: Complete sets and the polynomial-time hierarchy
description: scientific article; zbMATH DE number 3720354