Positive Turing and truth-table completeness for NEXP are incomparable

DOI10.1007/BFB0055797MaRDI QIDQ4218121zbMATH OpenFDO

Authors Levke Bentzien

Publication date 15 July 1999

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

Full work available at URL https://doi.org/10.1007/BFB0055797

zbMATH Keywords

\({\mathbf N}{\mathbf E}{\mathbf X}{\mathbf P}\)many-one completenesspositive Turing completenessreducibilitiestruth-table completenesstt-completeness

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Structural properties of nonautoreducible sets
• Completeness for nondeterministic complexity classes
• scientific article; zbMATH DE number 6691435
• Separation of NP-completeness notions
• A note on complete problems for complexity classes

Cited in

(1)

• A comparison of polynomial time completeness notions

This page was built for publication: Positive Turing and truth-table completeness for NEXP are incomparable

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