Diagonalizations over polynomial time computable sets

DOI10.1016/0304-3975(87)90053-3zbMath0653.03028OpenAlexW2004243323MaRDI QIDQ1107526

Hans Fleischhack, Hagen Huwig, Ambos-Spies, Klaus

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90053-3

zbMATH Keywords

diagonalizationNPp-generic setsp-immunitypolynomial time computable functionspolynomial time computable sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (20)

Almost every set in exponential time is P-bi-immune ⋮ Genericity and measure for exponential time ⋮ Polynomial terse sets ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ A thirty year old conjecture about promise problems ⋮ Index sets and presentations of complexity classes ⋮ Autoreducibility, mitoticity, and immunity ⋮ Resource bounded randomness and weakly complete problems ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Autoreducibility of NP-complete sets under strong hypotheses ⋮ Relativized isomorphisms of NP-complete sets ⋮ Inseparability and strong hypotheses for disjoint NP pairs ⋮ Non-mitotic Sets ⋮ Non-mitotic sets ⋮ Genericity and randomness over feasible probability measures ⋮ Genericity and measure for exponential time ⋮ Genericity, Randomness, and Polynomial-Time Approximations ⋮ Resource bounded immunity and simplicity ⋮ Feasible analysis, randomness, and base invariance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Indexings of subrecursive classes
• 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
• A uniform approach to obtain diagonal sets in complexity classes
• A comparison of polynomial time reducibilities
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Recursively enumerable generic sets
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP

This page was built for publication: Diagonalizations over polynomial time computable sets