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)

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

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)