Collapsing degrees via strong computation
From MaRDI portal
Publication:2366690
DOI10.1016/0022-0000(93)90009-LzbMath0771.68052OpenAlexW1998913435MaRDI QIDQ2366690
Albrecht Hoene, Hemaspaandra, Lane A.
Publication date: 18 August 1993
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(93)90009-l
Related Items (1)
Cites Work
- Strong nondeterministic polynomial-time reducibilities
- Qualitative relativizations of complexity classes
- On one-one polynomial time equivalence relations
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- On one-way functions and polynomial-time isomorphisms
- The method of forced enumeration for nondeterministic automata
- Isomorphisms and 1-L reductions
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- Using inductive counting to simulate nondeterministic computation
- Relative complexity of checking and evaluating
- On log-tape isomorphisms of complete sets
- Relationships between nondeterministic and deterministic tape complexities
- One-way functions and the nonisomorphism of NP-complete sets
- On the unique satisfiability problem
- Complexity Measures for Public-Key Cryptosystems
- Nondeterministic Space is Closed under Complementation
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Completeness for nondeterministic complexity classes
- Complete Problems and Strong Polynomial Reducibilities
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Polynomial Time Enumeration Reducibility
- The isomorphism conjecture fails relative to a random oracle
- Unnamed Item
- Unnamed Item
This page was built for publication: Collapsing degrees via strong computation
