A second step toward the strong polynomial-time hierarchy
From MaRDI portal
Publication:3816982
Recommendations
- Strong time bounds: Non-computable bounds and a hierarchy theorem
- Strong polynomial-time reducibility
- Proper hierarchies in polylogarithmic time and absence of complete problems
- A time-space hierarchy between polynomial time and polynomial space
- Structures computable in polynomial time. II
- Polynomial-time hierarchies on some classes of functions. II
- A second step towards complexity-theoretic analogs of Rice's Theorem
- scientific article; zbMATH DE number 4119625
- A weak constructive second-order arithmetic with extraction of algorithms computable in polynomial time
- Strong computational lower bounds via parameterized complexity
Cites work
- scientific article; zbMATH DE number 3883611 (Why is no real title available?)
- scientific article; zbMATH DE number 719756 (Why is no real title available?)
- A second step toward the polynomial hierarchy
- Complete sets and the polynomial-time hierarchy
- Immunity, Relativizations, and Nondeterminism
- Oracle-dependent properties of the lattice of NP sets
- Parity, circuits, and the polynomial-time hierarchy
- Recursive Predicates and Quantifiers
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations comparing NP and exponential time
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Simplicity, Relativizations and Nondeterminism
- Simplicity, immunity, relativizations and nondeterminism
- The polynomial-time hierarchy
Cited in
(6)- Strong time bounds: Non-computable bounds and a hierarchy theorem
- Resource bounded immunity and simplicity
- A note on separating the relativized polynomial time hierarchy by immune sets
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- More on BPP and the polynomial-time hierarchy
- Relativization of Gurevich’s Conjectures
This page was built for publication: A second step toward the strong polynomial-time hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3816982)
