Diagonalizations over polynomial time computable sets
From MaRDI portal
(Redirected from Publication:1107526)
A formal notion of diagonalization is developed which allows to enforce properties that are related to the class of polynomial time computable sets (the class of polynomial time computable functions respectively), like, e.g., p-immunity. It is shown that there are sets - called p- generic - which have all properties enforceable by such diagonalizations. We study the behaviour and the complexity of p-generic sets. In particular, we show that the existence of p-generic sets in NP is oracle dependent, even if we assume \(P\neq NP\).
Recommendations
Cites work
- A comparison of polynomial time reducibilities
- A note on structure and looking back applied to the relative complexity of computable functions
- A uniform approach to obtain diagonal sets in complexity classes
- scientific article; zbMATH DE number 3883611 (Why is no real title available?)
- scientific article; zbMATH DE number 3885884 (Why is no real title available?)
- scientific article; zbMATH DE number 3861137 (Why is no real title available?)
- scientific article; zbMATH DE number 3869312 (Why is no real title available?)
- scientific article; zbMATH DE number 3954889 (Why is no real title available?)
- scientific article; zbMATH DE number 3987265 (Why is no real title available?)
- scientific article; zbMATH DE number 4091484 (Why is no real title available?)
- scientific article; zbMATH DE number 817509 (Why is no real title available?)
- Indexings of subrecursive classes
- On the Structure of Polynomial Time Reducibility
- On the structure of sets in NP and other complexity classes
- Oracle-dependent properties of the lattice of NP sets
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Recursively enumerable generic sets
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
Cited in
(29)- Non-mitotic sets
- Polynomial terse sets
- Genericity and randomness over feasible probability measures
- Almost every set in exponential time is P-bi-immune
- Genericity and measure for exponential time
- Index sets and presentations of complexity classes
- Resource bounded randomness and weakly complete problems
- Autoreducibility of NP-complete sets under strong hypotheses
- Feasible analysis, randomness, and base invariance
- Bounded truth table does not reduce the one-query tautologies to a random oracle
- Resource bounded immunity and simplicity
- A thirty year old conjecture about promise problems
- scientific article; zbMATH DE number 3988707 (Why is no real title available?)
- scientific article; zbMATH DE number 3987265 (Why is no real title available?)
- Genericity, Randomness, and Polynomial-Time Approximations
- scientific article; zbMATH DE number 4121422 (Why is no real title available?)
- scientific article; zbMATH DE number 1860655 (Why is no real title available?)
- Diagonalization in proof complexity
- scientific article; zbMATH DE number 841081 (Why is no real title available?)
- Genericity and measure for exponential time (extended abstract)
- The Complexity of the Diagonal Problem for Recursion Schemes
- Joining non-low C.E. sets with diagonally non-computable functions
- Non-mitotic Sets
- Diagonalisation and Church's Thesis: Kleene's Homework
- Relativized isomorphisms of NP-complete sets
- Inseparability and strong hypotheses for disjoint NP pairs
- Autoreducibility, mitoticity, and immunity
- Honest polynomial time reducibilities and the \(P=?NP\) problem
- Does truth-table of linear norm reduce the one-query tautologies to a random oracle?
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)
