Upward separation for FewP and related classes

DOI10.1016/0020-0190(94)90123-6zbMath0938.68662OpenAlexW1999546142MaRDI QIDQ1341678

Jörg Rothe, Osamu Watanabe, Rajesh P. N. Rao

Publication date: 16 February 1995

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90123-6

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

One-way permutations and self-witnessing languages ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ A downward translation in the polynomial hierarchy ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ A note on P-selective sets and closeness ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ A Downward Collapse within the Polynomial Hierarchy ⋮ Tally NP sets and easy census functions. ⋮ Restrictive Acceptance Suffices for Equivalence Problems

Cites Work

• Gap-definable counting classes

This page was built for publication: Upward separation for FewP and related classes