An unambiguous class possessing a complete set

DOI10.1007/BFB0023471MaRDI QIDQ5048936zbMATH OpenOpenAlexFDO

Authors Klaus-Jörn Lange

Publication date 9 November 2022

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

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

Mathematics Subject Classification ID

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

Recommendations

• Making Nondeterminism Unambiguous
• Complexity classes without machines: on complete languages for UP
• scientific article; zbMATH DE number 1335888
• Unambiguity of circuits
• Promise problems complete for complexity classes

Cites work

• scientific article; zbMATH DE number 437524 (Why is no real title available?)
• scientific article; zbMATH DE number 3896918 (Why is no real title available?)
• scientific article; zbMATH DE number 3960999 (Why is no real title available?)
• scientific article; zbMATH DE number 1256637 (Why is no real title available?)
• scientific article; zbMATH DE number 1306867 (Why is no real title available?)
• scientific article; zbMATH DE number 1346519 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Complexity classes without machines: on complete languages for UP
• Nondeterministic Space is Closed under Complementation
• Riemann's hypothesis and tests for primality
• Symmetric space-bounded computation
• The method of forced enumeration for nondeterministic automata
• Time/Space Trade-Offs for Reversible Computation

Cited in

(4)

• NL-printable sets and nondeterministic Kolmogorov complexity
• Depth-first search in directed planar graphs, revisited
• \textsc{ReachFewL} = \textsc{ReachUL}
• NL-printable sets and nondeterministic Kolmogorov complexity

This page was built for publication: An unambiguous class possessing a complete set

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