Limitations of the upward separation technique

DOI10.1007/BF02090390zbMath0708.68019OpenAlexW1979549874MaRDI QIDQ3490941

Eric W. Allender

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1007/bf02090390

zbMATH Keywords

nondeterminismTally setultra sparse setupward separation technique

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Space-efficient recognition of sparse self-reducible languages, A downward translation in the polynomial hierarchy, Unnamed Item, Upward separations and weaker hypotheses in resource-bounded measure, A Downward Collapse within the Polynomial Hierarchy, Tally NP sets and easy census functions., Sparse sets and collapse of complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Downward translations of equality
• On hardness of one-way functions
• On sparse sets in NP-P
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• On the unique satisfiability problem
• Sparse Sets in : Relativizations
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• On relativized exponential and probabilistic complexity classes
• Relativizing Time, Space, and Time-Space
• P-Printable Sets
• Tally languages and complexity classes