Separating NE from Some Nonuniform Nondeterministic Complexity Classes

DOI10.1007/978-3-642-02882-3_48MaRDI QIDQ5323096zbMATH OpenOpenAlexFDO

Authors Bin Fu, Liyu Zhang, Angsheng Li

Publication date 23 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02882-3_48

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Separating NE from some nonuniform nondeterministic complexity classes
• NE is not NP Turing reducible to nonexponentially dense NP sets
• scientific article; zbMATH DE number 4075037
• scientific article; zbMATH DE number 3926243
• Some consequences of non-uniform conditions on uniform classes

Cites work

• A hierarchy for nondeterministic time complexity
• Complete Problems and Strong Polynomial Reducibilities
• Computability and complexity theory
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On Isomorphisms and Density of NP and Other Complete Sets
• On lower bounds of the closeness between complexity classes
• On sets Turing reducible to p-selective sets
• On the reducibility of sets inside NP to sets with low information content
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Separating classes in the exponential-time hierarchy from classes in PH
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Theory of semi-feasible algorithms

Cited in

(5)

• NE is not NP Turing reducible to nonexponentially dense NP sets
• scientific article; zbMATH DE number 4041256 (Why is no real title available?)
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• Separating NE from some nonuniform nondeterministic complexity classes
• Avoiding simplicity is complex

This page was built for publication: Separating NE from Some Nonuniform Nondeterministic Complexity Classes

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