On the structure of sets in NP and other complexity classes

DOI10.1016/0304-3975(81)90069-4MaRDI QIDQ1162811zbMATH OpenOpenAlexFDO

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

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

NP-completenessreducibility

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3594673 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3431764 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Note on Sparse Complete Sets
• Minimal pairs of polynomial degrees with subexponential complexity
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On Reducibility to Complex or Sparse Sets
• On the Structure of Polynomial Time Reducibility
• On the structure of sets in NP and other complexity classes
• Recursive Properties of Abstract Complexity Classes
• The complexity of theorem-proving procedures
• The honest subrecursive classes are a lattice

Cited in

(28)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1162811)