A second step toward the strong polynomial-time hierarchy

DOI10.1007/BF02088009zbMATH Open0665.68039MaRDI QIDQ3816982FDOQ3816982

Authors: Leen Torenvliet 

Publication date: 1988

Published in: Mathematical Systems Theory (Search for Journal in Brave)

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

zbMATH Keywords

immunityoraclessimple setsbi-immunitystrong separation of low levels of the polynomial hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• The polynomial-time hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• Title not available (Why is that?)
• Relativizations comparing NP and exponential time
• Complete sets and the polynomial-time hierarchy
• Recursive Predicates and Quantifiers
• 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?)
• Immunity, Relativizations, and Nondeterminism
• Oracle-dependent properties of the lattice of NP sets
• Simplicity, Relativizations and Nondeterminism
• A second step toward the polynomial hierarchy
• Simplicity, immunity, relativizations and nondeterminism

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)