Limitations of the upward separation technique
- 1 December 1991
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 24 (1), 53-67
- https://doi.org/10.1007/bf02090390
Abstract
No abstract availableKeywords
This publication has 21 references indexed in Scilit:
- Generalized kolmogorov complexity in relativized separationsPublished by Springer Nature ,2005
- On the power of parity polynomial timePublished by Springer Nature ,2005
- Limitations of the upward separation technique (preliminary version)Published by Springer Nature ,1989
- On hardness of one-way functionsInformation Processing Letters, 1988
- On relativized exponential and probabilistic complexity classesInformation and Control, 1986
- Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEPMathematical Logic Quarterly, 1986
- On sparse sets in NP–PInformation Processing Letters, 1983
- On the unique satisfiability problemInformation and Control, 1982
- On-line simulation of k + 1 tapes by k tapes requires nonlinear timeInformation and Control, 1982
- Tally languages and complexity classesInformation and Control, 1974