On models of a nondeterministic computation

Details On models of a nondeterministic computation On models of a nondeterministic computation

2008-11-16

arxiv.org/abs/0811.2586v1

Computer Science

Computational Complexity

Scientific paper

In this paper we consider a nondeterministic computation by deterministic multi-head 2-way automata having a read-only access to an auxiliary memory. The memory contains additional data (a guess) and computation is successful iff it is successful for some memory content. Also we consider the case of restricted guesses in which a guess should satisfy some constraint. We show that the standard complexity classes such as L, NL, P, NP, PSPACE can be characterized in terms of these models of nondeterministic computation. These characterizations differ from the well-known ones by absence of alternation.

Affiliated with

Also associated with

No associations

Rating

On models of a nondeterministic computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On models of a nondeterministic computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On models of a nondeterministic computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-331616