Computations with a restricted number of nondeterministic steps (Extended Abstract)

1 January 1977

proceedings article
Published by Association for Computing Machinery (ACM)

p. 178-185
https://doi.org/10.1145/800105.803407

Abstract

Nondeterminism is one of the most elusive concepts in computing. In this paper we direct our efforts towards viewing nondeterminism as an additional resource at the disposal of time or space bounded Turing machine computations and study the classes of languages acceptable by these machines with restricted amounts of nondeterminism. One motivation for this study comes from the observation that for many of the well-known NP-complete problems, if n' is the length of the input, an algorithm exists requiring a total number of moves which is polynomial in n, but the number of nondeterministic moves is only linear in n.

Keywords

RESTRICTED NUMBER
TOTAL NUMBER
EXTENDED ABSTRACT
WELL-KNOWN NP-COMPLETE PROBLEM
NONDETERMINISTIC MOVE
TURING MACHINE COMPUTATION
ELUSIVE CONCEPT
NONDETERMINISTIC STEP
ADDITIONAL RESOURCE
RESTRICTED AMOUNT
TURING MACHINE
DYNAMIC PROGRAMMING
NP COMPLETE PROBLEM
PRINCIPLE OF OPTIMALITY
LOWER BOUND
DECOMPOSITION
NONDETERMINISTIC ALGORITHM

This publication has 0 references indexed in Scilit: