A uniform approach to obtain diagonal sets in complexity classes

DOI10.1016/0304-3975(82)90114-1MaRDI QIDQ1164414zbMATH OpenOpenAlexFDO

Authors Uwe Schöning

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

almost polynomial timeAPTco-NPNPPpolynomial hierarchyPSPACErandom polynomial timesets which diagonalize over certain complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• A note on structure and looking back applied to the relative complexity of computable functions
• Complete sets and the polynomial-time hierarchy
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3594673 (Why is no real title available?)
• On the Structure of Polynomial Time Reducibility
• On the structure of sets in NP and other complexity classes
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Strong nondeterministic polynomial-time reducibilities
• The complexity of theorem-proving procedures
• The polynomial-time hierarchy

Cited in

(28)

• A low and a high hierarchy within NP
• Qualitative relativizations of complexity classes
• The recursion-theoretic structure of complexity classes
• Independence results about context-free languages and lower bounds
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On \(\Delta ^ P_ 2\)-immunity
• Honest polynomial degrees and \(P=?NP\)
• Diagonalizations over polynomial time computable sets
• On the relative complexity of hard problems for complexity classes without complete problems
• 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
• Minimal pairs and complete problems
• Index sets and presentations of complexity classes
• Gap-languages and log-time complexity classes
• Structural properties of bounded relations with an application to NP optimization problems
• Uniformly hard languages.
• A note on non-complete problems in \(NP_\mathbb{R}\)
• Constructing NP-intermediate problems by blowing holes with parameters of various properties
• Generality's price: Inescapable deficiencies in machine-learned programs
• 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
• Some structural complexity results for \(\exists{\mathbb{R}} \)
• On the structure of \(\Delta_ 2\!^ p\)
• Minimal pairs for P
• Canonical disjoint NP-pairs of propositional proof systems
• Honest polynomial time reducibilities and the \(P=?NP\) problem

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

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