Diagonalizations over polynomial time computable sets
From MaRDI portal
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)
