using non determinstic TM to prove NP is closed under kleene closure
- From: "wbsurfver@xxxxxxxxx" <wbsurfver@xxxxxxxxx>
- Date: 8 Dec 2006 16:18:59 -0800
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, I find I naturaly
seem to imagine a NDTM as a parallel process or forking sort of
operation. 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. This implies that the children and parents can all
communicate, that a NDTM path can split itself multiple times and so
on. This seems to me to be equivallent to a NDTM, but I just want to
make sure the teacher dosen't decide I have not followed comp theory by
trying to get a NDTM to do something I am not supposed to etc.
.
- Follow-Ups:
- Re: using non determinstic TM to prove NP is closed under kleene closure
- From: Chris Smith
- Re: using non determinstic TM to prove NP is closed under kleene closure
- Prev by Date: Re: Regular Tree Grammar vs. Context-Free Grammar
- Next by Date: Re: An easy way to prove P != NP
- Previous by thread: Re: Question on computational complexity
- Next by thread: Re: using non determinstic TM to prove NP is closed under kleene closure
- Index(es):
Relevant Pages
|
