A uniform approach to obtain diagonal sets in complexity classes

DOI10.1016/0304-3975(82)90114-1zbMath0485.68039OpenAlexW2082636129MaRDI QIDQ1164414

Uwe Schoening

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90114-1

zbMATH Keywords

polynomial hierarchyPSPACEAPTNPPrandom polynomial timealmost polynomial timeco-NPsets which diagonalize over certain complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (27)

Uniformly hard languages. ⋮ Some remarks on witness functions for nonpolynomial and noncomplete sets in NP ⋮ Minimal pairs and complete problems ⋮ On \(\Delta ^ P_ 2\)-immunity ⋮ Generality's price: Inescapable deficiencies in machine-learned programs ⋮ Honest polynomial degrees and \(P=?NP\) ⋮ 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 ⋮ Canonical disjoint NP-pairs of propositional proof systems ⋮ Gap-languages and log-time complexity classes ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ A note on non-complete problems in \(NP_\mathbb{R}\) ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ A uniform approach to define complexity classes ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Nondiamond theorems for polynomial time reducibility ⋮ An explicit solution to Post's problem over the reals ⋮ Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998 ⋮ On the structure of \(\Delta_ 2\!^ p\) ⋮ A low and a high hierarchy within NP ⋮ Structural properties of bounded relations with an application to NP optimization problems ⋮ Minimal pairs for P ⋮ Qualitative relativizations of complexity classes ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Strong nondeterministic polynomial-time reducibilities
• 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
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• On the Structure of Polynomial Time Reducibility
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• The complexity of theorem-proving procedures

This page was built for publication: A uniform approach to obtain diagonal sets in complexity classes