On the structure of sets in NP and other complexity classes

DOI10.1016/0304-3975(81)90069-4zbMath0482.68042OpenAlexW2009972827MaRDI QIDQ1162811

Lawrence H. Landweber, Edward L. Robertson, Richard J. Lipton

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://digital.library.wisc.edu/1793/58126

zbMATH Keywords

reducibilityNP-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of computability and recursion theory (03D80) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (28)

Uniformly hard languages. ⋮ A complexity theory for feasible closure properties ⋮ Generality's price: Inescapable deficiencies in machine-learned programs ⋮ The structure of the honest polynomial m-degrees ⋮ Diagonalizations over polynomial time computable sets ⋮ Index sets and presentations of complexity classes ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ The theory of the polynomial many-one degrees of recursive sets is undecidable ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ A note on structure and looking back applied to the relative complexity of computable functions ⋮ On the structure of sets in NP and other complexity classes ⋮ A uniform approach to obtain diagonal sets in complexity classes ⋮ Reductions on NP and p-selective sets ⋮ The complexity types of computable sets ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Nondiamond theorems for polynomial time reducibility ⋮ On Complete Problems, Relativizations and Logics for Complexity Classes ⋮ Undecidability results for low complexity time classes ⋮ On the structure of \(\Delta_ 2\!^ p\) ⋮ Structural properties of bounded relations with an application to NP optimization problems ⋮ Polynomial time computations in models of ET ⋮ Minimal pairs for P ⋮ On an optimal propositional proof system and the structure of easy subsets of TAUT. ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties ⋮ The recursion-theoretic structure of complexity classes ⋮ Independence results about context-free languages and lower bounds ⋮ Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the structure of sets in NP and other complexity classes
• Minimal pairs of polynomial degrees with subexponential complexity
• A Note on Sparse Complete Sets
• The honest subrecursive classes are a lattice
• On Reducibility to Complex or Sparse Sets
• On the Structure of Polynomial Time Reducibility
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The complexity of theorem-proving procedures
• Recursive Properties of Abstract Complexity Classes

This page was built for publication: On the structure of sets in NP and other complexity classes