Collapsing degrees via strong computation

DOI10.1016/0022-0000(93)90009-LMaRDI QIDQ2366690zbMATH OpenOpenAlexFDO

Authors Albrecht Hoene, Lane A. Hemaspaandra

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, http://hdl.handle.net/1802/5031

zbMATH Keywords

collapses for sublinear nondeterministic space degreesP-isomorphic

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Collapsing degrees via strong computation
• Collapsing degrees
• scientific article; zbMATH DE number 1420830
• Relativized isomorphisms of NP-complete sets

Cites work

• Complete Problems and Strong Polynomial Reducibilities
• Completeness for nondeterministic complexity classes
• Complexity Measures for Public-Key Cryptosystems
• scientific article; zbMATH DE number 4029534 (Why is no real title available?)
• scientific article; zbMATH DE number 3596249 (Why is no real title available?)
• Isomorphisms and 1-L reductions
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Nondeterministic Space is Closed under Complementation
• On Isomorphisms and Density of NP and Other Complete Sets
• On log-tape isomorphisms of complete sets
• On one-one polynomial time equivalence relations
• On one-way functions and polynomial-time isomorphisms
• On the unique satisfiability problem
• One-way functions and the nonisomorphism of NP-complete sets
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• Polynomial Time Enumeration Reducibility
• Qualitative relativizations of complexity classes
• Relationships between nondeterministic and deterministic tape complexities
• Relative complexity of checking and evaluating
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Strong nondeterministic polynomial-time reducibilities
• The isomorphism conjecture fails relative to a random oracle
• The method of forced enumeration for nondeterministic automata
• Using inductive counting to simulate nondeterministic computation

Cited in

(6)

• Collapsing degrees
• DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
• Investigations concerning the structure of complete sets
• Collapsing degrees via strong computation
• scientific article; zbMATH DE number 1420830 (Why is no real title available?)
• scientific article; zbMATH DE number 6470115 (Why is no real title available?)

This page was built for publication: Collapsing degrees via strong computation

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