Nondeterministic Time and Space Complexity Classes

The marginal utility of the Turing machine computational resources running time and storage space are studied. A technique is developed which, unlike diagonalization, applies equally well to nondeterministic and deterministic automata. For f, g time or space bounding functions with f (n+1) small c...

ver descrição completa

Detalhes bibliográficos
Autor principal: Seiferas, Joel Irvin
Outros Autores: Meyer, Albert R.
Publicado em: 2023
Acesso em linha:https://hdl.handle.net/1721.1/149437