Diagonalizations over polynomial time computable sets
DOI10.1016/0304-3975(87)90053-3zbMATH Open0653.03028OpenAlexW2004243323MaRDI QIDQ1107526FDOQ1107526
Authors: Hans Fleischhack, Hagen Huwig, Klaus Ambos-Spies 
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
Recommendations
diagonalizationNPp-generic setsp-immunitypolynomial time computable functionspolynomial time computable sets
Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- On the Structure of Polynomial Time Reducibility
- Title not available (Why is that?)
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- A comparison of polynomial time reducibilities
- Title not available (Why is that?)
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Title not available (Why is that?)
- Oracle-dependent properties of the lattice of NP sets
- Title not available (Why is that?)
- Recursively enumerable generic sets
- Indexings of subrecursive classes
- On the structure of sets in NP and other complexity classes
- A uniform approach to obtain diagonal sets in complexity classes
- A note on structure and looking back applied to the relative complexity of computable functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (29)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Honest polynomial time reducibilities and the \(P=?NP\) problem
- Genericity, Randomness, and Polynomial-Time Approximations
- Polynomial terse sets
- The Complexity of the Diagonal Problem for Recursion Schemes
- Inseparability and strong hypotheses for disjoint NP pairs
- Title not available (Why is that?)
- Resource bounded immunity and simplicity
- Genericity and randomness over feasible probability measures
- Bounded truth table does not reduce the one-query tautologies to a random oracle
- Autoreducibility of NP-complete sets under strong hypotheses
- Joining non-low C.E. sets with diagonally non-computable functions
- Autoreducibility, mitoticity, and immunity
- Non-mitotic sets
- Non-mitotic Sets
- Almost every set in exponential time is P-bi-immune
- Index sets and presentations of complexity classes
- A thirty year old conjecture about promise problems
- Title not available (Why is that?)
- Feasible analysis, randomness, and base invariance
- Genericity and measure for exponential time
- Resource bounded randomness and weakly complete problems
- Title not available (Why is that?)
- Diagonalisation and Church's Thesis: Kleene's Homework
- Does truth-table of linear norm reduce the one-query tautologies to a random oracle?
- Genericity and measure for exponential time (extended abstract)
- Diagonalization in proof complexity
- Relativized isomorphisms of NP-complete sets
This page was built for publication: Diagonalizations over polynomial time computable sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107526)
