Nondeterministic separations

DOI10.1007/978-3-319-17142-5_2MaRDI QIDQ2948449zbMATH OpenOpenAlexFDO

Authors Lance Fortnow

Publication date 30 September 2015

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

Full work available at URL https://doi.org/10.1007/978-3-319-17142-5_2

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1335875
• New non-uniform lower bounds for uniform classes
• Nondeterministic Communication with a Limited Number of Advice Bits
• Refining Nondeterminism in Relativizations of Complexity Classes
• scientific article; zbMATH DE number 4074483

Cited in

(2)

• Separation of the monotone NC hierarchy
• Deciding separability with a fixed error

This page was built for publication: Nondeterministic separations

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