Limitations of the upward separation technique

DOI10.1007/BF02090390MaRDI QIDQ3490941zbMATHOpenAlexFDO

Authors Eric 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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 3265246
• Limitations imposed by complementarity
• Limitations of dominance and forward induction:
• Limitations of the Even-Mansour construction
• Limitations on isotropic yield criteria
• Limitations of VCG-based mechanisms
• Limitations of VCG-based mechanisms

Cites work

• scientific article; zbMATH DE number 3926243 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 18632 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3530978 (Why is no real title available?)
• Downward translations of equality
• On hardness of one-way functions
• On relativized exponential and probabilistic complexity classes
• On sparse sets in NP-P
• On the unique satisfiability problem
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• P-Printable Sets
• Relativizing Time, Space, and Time-Space
• Sparse Sets in : Relativizations
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Tally languages and complexity classes

Cited in

(8)

• Space-efficient recognition of sparse self-reducible languages
• Defying upward and downward separation
• scientific article; zbMATH DE number 7378390 (Why is no real title available?)
• Upward separations and weaker hypotheses in resource-bounded measure
• A Downward Collapse within the Polynomial Hierarchy
• A downward translation in the polynomial hierarchy
• Sparse sets and collapse of complexity classes
• Tally NP sets and easy census functions.

This page was built for publication: Limitations of the upward separation technique

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