A nondeterministic Turing machine variant to compute functions

DOI10.1016/J.TCS.2021.12.008MaRDI QIDQ2067632zbMATH OpenOpenAlexFDO

Authors João Guilherme Fritsche Colombo, Jerusa Marchi

Publication date 18 January 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.12.008

zbMATH Keywords

computable functionscounting Turing machinesdivide and conquernondeterministic Turing machinespolynomial spacetime complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• scientific article; zbMATH DE number 3903969
• Deciding according to the shortest computations
• Functions computable in polynomial space
• On nondeterminism in parallel computation
• scientific article; zbMATH DE number 1993590

Cites work

• Alternation
• Computational Complexity
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Introduction to algorithms.
• The complexity of computing the permanent
• The complexity of optimization problems

This page was built for publication: A nondeterministic Turing machine variant to compute functions

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