A note on deterministic and nondeterministic time complexity

DOI10.1016/S0019-9958(82)90515-0MaRDI QIDQ3331208zbMATH OpenOpenAlexFDO

Authors Shimon Even, Timothy J. Long, Yacov Yacobi

Publication date 1982

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0019-9958(82)90515-0

zbMATH Keywords

co-NP problemsdeterministic computationsnondeterministic computationsnondeterministic time complexityNP-problemsTuring machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Deterministic versus nondeterministic time and lower bound problems
• Almost-everywhere complexity hierarchies for nondeterministic time
• A Note on Randomized Polynomial Time
• scientific article; zbMATH DE number 4205978
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
• A note on the best-case complexity
• scientific article; zbMATH DE number 4092762
• Descriptive complexity of deterministic polylogarithmic time
• On lower bounds for the time of computation
• scientific article; zbMATH DE number 2068877

Cited in

(2)

• Almost-everywhere complexity hierarchies for nondeterministic time
• scientific article; zbMATH DE number 4205978 (Why is no real title available?)

This page was built for publication: A note on deterministic and nondeterministic time complexity

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