Limitations of the upward separation technique

DOI10.1007/BF02090390MaRDI QIDQ3490941zbMATH OpenOpenAlexFDO

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

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

• Downward translations of equality
• 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?)
• 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

(9)

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

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)