Some hierarchies of relativized time-bounded complexity classes

DOI10.2977/PRIMS/1195179054MaRDI QIDQ1070822zbMATH OpenOpenAlexFDO

Authors Hisao Tanaka, Masa-aki Izumi, Nobuyuki Takahashi

Publication date 1985

Published in Publications of the Research Institute for Mathematical Sciences, Kyoto University (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2977/prims/1195179054

zbMATH Keywords

complexity subclasses of relativized NPoracle set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4011940
• On relativized nondeterministic polynomial-time bounded computations
• scientific article; zbMATH DE number 3958736
• Oracles for Deterministic Versus Alternating Classes
• Relativizations comparing NP and exponential time

Cited in

(7)

• Almost-everywhere complexity hierarchies for nondeterministic time
• Determining the levels of some special complexity classes of sets in the Kleene arithmetical hierarchy
• Relating the bounded arithmetic and polynomial time hierarchies
• On relativized nondeterministic polynomial-time bounded computations
• scientific article; zbMATH DE number 3958736 (Why is no real title available?)
• On Tally Relativizations of $BP$-Complexity Classes
• A time-space hierarchy between polynomial time and polynomial space

This page was built for publication: Some hierarchies of relativized time-bounded complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1070822)