Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Deterministic vs Nondeterministic Turing machines.
0 views
Skip to first unread message
Dmitriy Samsonov
Oct 6, 2008, 8:53:09 AM10/6/08
to
... first of all, is there any generally accepted definition of non-
deterministic Turing Machines? At least I have found almost nothing
usable, including wiki-articles. So I will state my question in the
following form:
deterministic Turing Machines? At least I have found almost nothing
usable, including wiki-articles. So I will state my question in the
following form:
Is it true, that there exists ‘probabilistic’-TM, which could not be
simulated with deterministic-TM at all?
Is it true, that there exists ‘probabilistic’-TM, which could not be
simulated effectively with deterministic-TM?
Why negative answer at least on second question could be used as proof
of P!=NP?
If one can give a link, or cite usable definition of non-deterministic
TM, questions should be formulated for non-deterministic TM.
0 new messages