Re: using non determinstic TM to prove NP is closed under kleene closure

wbsurfver@xxxxxxxxx <wbsurfver@xxxxxxxxx> wrote:
I was looking at the definiton of a non deterministic TM, which
apparently there are varations. For me to prove my homework problem
that NP is closed under L* where L is NP, it seems easiest if I can use
a proof where a NDTM that can split itself into many branches and
possibly each of those branches could split again,

Yep. That is probably the most common way to define an NDTM.

The trick in my proof however is just that each parallel
computation path can communicate with the others, so I can say that for
instance I branched initially into k parents, and each of those k
parents splits itself again into a secondary layer so that each k
parent has a further number of children processes. If for some parent
all of it's children accepted their inputs then that parent accepts
it's input.

That may not be okay, though. A given configuration of an NDTM accepts
if an accepting state is reachable -- that is, if any one of its child
configurations accepts, NOT if all of its child configurations accept.

Another variation on Turing machines, called alternating Turing
machines, allows you to require that all children accept; and
alternating Turing machines are equivalent to TMs in terms of
computability. However, if your assignment is to use NDTMs to prove
this, then using ATMs would probably not be okay.

This implies that the children and parents can all
communicate, that a NDTM path can split itself multiple times and so
on.

I wouldn't think of it as "nodes" communicating. The nodes are just
configurations in a computation history, and the "communication" is just
a natural propogation of the accept conditions, based on the definition
of how the machine computes.

It's entirely normal for an NDTM to split its path several times. Is
there some definition being used in your course that implies otherwise?

--
Chris Smith
.