On the structure of sets in NP and other complexity classes

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

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

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
Generality's price: Inescapable deficiencies in machine-learned programs
The complexity types of computable sets
On the structure of $\Delta_ 2\!^ p$
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
The theory of the polynomial many-one degrees of recursive sets is undecidable
Diagonalizations over polynomial time computable sets
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)