Limitations of the upward separation technique
From MaRDI portal
Publication:3490941
DOI10.1007/BF02090390zbMATH Open0708.68019OpenAlexW1979549874MaRDI QIDQ3490941FDOQ3490941
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
Recommendations
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tally languages and complexity classes
- On sparse sets in NP-P
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- On hardness of one-way functions
- P-Printable Sets
- On the unique satisfiability problem
- On relativized exponential and probabilistic complexity classes
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- Relativizing Time, Space, and Time-Space
- Title not available (Why is that?)
- Sparse Sets in : Relativizations
- Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
- Downward translations of equality
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (8)
- A downward translation in the polynomial hierarchy
- Tally NP sets and easy census functions.
- Defying upward and downward separation
- Upward separations and weaker hypotheses in resource-bounded measure
- Sparse sets and collapse of complexity classes
- Title not available (Why is that?)
- A Downward Collapse within the Polynomial Hierarchy
- Space-efficient recognition of sparse self-reducible languages
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)
