Prev: *** Evening Seminar by Prof Mike Hinchey, 28 Jan, UK: Evolving Critical Systems
Next: Algorithmic Random Oracle
From: Stephan Lukits on 13 Jan 2010 08:42
Hi, I don't get the motivation for the
informal definition of "polynomial time"-
nondeterministic-algorithm:

A nondeterministic algorithm that solves
a decision problem \Pi is said to operate
in "polynomial time" if there exists a
polynomial p such that, for every instance
I from Y_\Pi, there is some guess S that
leads the deterministic checking stage to
respond "yes" for I and S within time
p(Length[I]).

Y_\Pi is the subset of words from the language
which is associated to the Problem \Pi and the
encoding e, where the algorithm returns "yes".

What I don't understand is the guessing aspect.
What if there are exponentially many structures
S (as a function of input length)? What if the
only right one of the exponentially many Structures
is guessed last? Or is always first the right one
guessed if there is one?

Best regards
Stephan
From: tchow on 13 Jan 2010 10:24
In article <hikik7$8c6$1(a)news-cedar.fernuni-hagen.de>,
Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>What I don't understand is the guessing aspect.
>What if there are exponentially many structures
>S (as a function of input length)? What if the
>only right one of the exponentially many Structures
>is guessed last? Or is always first the right one
>guessed if there is one?

It's important to recognize that the concept of a non-deterministic Turing
machine *is not supposed to be a plausible model of an actual machine one
might build*. In a way, the term "machine" is unfortunate, because that
suggests something an engineer might actually build. But this is not the
case here. As you point out, if we actually treated the definition as a
blueprint for building a physical device, we would scratch our heads over
how to implement the guessing, and wonder if that was really what the
architect intended.

Instead, the definition is an attempt to capture a *class of problems* that
commonly arise in practice. There are many problems with the property that
*if* we could guess the right answer somehow, then it would be *easy to
verify* that it is correct. This feature suggests a way to write down a
precise mathematical definition of this class of problems: We imagine a
hypothetical machine that "magically" guesses the right answer and then
verifies it in polynomial time. Such a machine exists only in our
imagination, but that is all we need for a *mathematical* definition (as
opposed to an engineering spec). Then we define NP to be the class of
problems that *could* be solved in polynomial time by such a machine, *if*
such a machine could be built.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Stephan Lukits on 13 Jan 2010 15:27
tchow(a)lsa.umich.edu schrieb:
> In article <hikik7$8c6$1(a)news-cedar.fernuni-hagen.de>,
> Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:

Thanks a lot for your detailed answer!

>> What I don't understand is the guessing aspect.
>> What if there are exponentially many structures
>> S (as a function of input length)? What if the
>> only right one of the exponentially many Structures
>> is guessed last? Or is always first the right one
>> guessed if there is one?
>
> [non-deterministic Turing machine is just an abstract concept]

I think, I recognized that. But it
nowhere said (in the book) that it
guesses the *right* structure if one
exists. To me it red, that the machine
just takes a guess, maybe right maybe
wrong. (Since English is not my mother
tongue I maybe missed something. I also
probably sound a bit clumsy because of that.)

BTW to me this definition looks not
very *mathematical*. There I have sets
and relations on it. (I'm studding
mathematics not engineering.) On a
more informal level I was told that a
NTM can solve (some) problems in
polynomial time where no polynomial
time algorithm on a DTM is known.
Solving a problem means to me that
the solution is somehow calculated
or proofed. Thus I'm not very convinced
by the idea of an oracled solution.

For the same reason I like the
idea more of a NTM which is defined
by a next move function which maps
to a set of sates in contrast to a
next move function of a DTM which
maps on a single state (-tuple). But
there the next move function has
to "choose" one of the states and no
one says (in a specific mathematical way)
how the next state should or could be
chosen?

Finally the most appealing approach to
me is to imagine a Machine which has the
the possibility to do countable parallel
steps in one step. Because there I can "see"
a way how to write an algorithm for the
traveling sales man (TSM) problem e.g. I just
build parallel the tree of all permutations.
I have for example for cities c1, c2, c3, c4
and a distance function a which maps two cities
to their distance. I built the tree from left
to right:


c1c2c3/ __ c1c2c3c4/
d(c1,c2)+d(c2,c3) d(c1,c2)+d(c2,c3)+d(...)
/
c1c2/d(c1,c2)
/ \
/ c1c2c4/ __ c1c2c4c3/
/ d(c1,c2)+d(c2,c4) d(c1,c2)+d(c2,c4)+d(...)
|
/
/ c1c3c2/ __ c1c3c2c4/
/ d(c1,c3)+d(c3,c2) d(c1,c3)+d(c3,c2)+d(...)
/ /
c1/0 ------ c1c3/d(c1,c3)
\ \
\ c1c3c4/ __ c1c3c4c2
\ d(c1,c3)+d(c3,c4) d(c1,c3)+d(c3,c4)+d(...)
\
|
\ c1c4c3/ __ c1c4c3c2/
\ d(c1,c4)+d(c4,c3) d(c1,c4)+d(c4,c3)+d(...)
\ /
c1c4/d(c1,c4)
\
c1c4c2/ __ c1c4c2c3/
d(c1,c4)+d(c4,c2) d(c1,c4)+d(c4,c2)+d(...)


1st level 2nd level 3rd level 4th level

Lets suppose an input string c1c2c3c4//5,3,1/2,4/6
To come from one level to the next one I
need to select an element of a "set", to
built the difference of two sets, and to
do a summation. I'm easily convinced that
I could develop DTMs which do this three
operations in polynomially time. If I now
assume that this operations can be done
parallel I'm convinced that I need only
polynomially time to go from one level to
the next level. Since the hight of such a
tree for n cities is n, the tree is done
within polynomially time. All which is
left is to find the minimum of n integers.
Again I'm easily assured that this can be
done in polynomially time. Thus all in all
I can with this imagination of a NTM *calculate*
the TSM-Problem within polynomially time. In
the above special case I could even imagine
having a real machine with 6-CPUs doing concrete
what I just sketched. This is what I mean when
I say that I can "see" that such a NTM machine
model is capable of solving a problem within
polynomially time while there is no DTM known
solving this problem within polynomially time.

Since this kind of NTMs aren't used I wonder
if there somewhere shines through the
oracle-Turing machine? Because polynomial
time verification of an oracled solution isn't
--- as I said --- persuasive to me yet.
(According to the claim that an NTM *solves*
problems like TSM in polynomial time)

best regards
Stephan
From: tchow on 13 Jan 2010 16:18
In article <hilabm$m1q$1(a)news-cedar.fernuni-hagen.de>,
Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>I think, I recognized that. But it
>nowhere said (in the book) that it
>guesses the *right* structure if one
>exists. To me it red, that the machine
>just takes a guess, maybe right maybe wrong.

Yes, that's correct. However, you also have to look at the definition of
what it means for the machine to accept the input. It accepts the input
if there is *some* accepting path.

Again, don't think of it as an actual machine that is limited to "doing one
thing at a time." The machine makes a guess, maybe right, maybe wrong. We,
like proud parents of a child, are very generous and consider that the
machine "succeeds" as long as *some* guess succeeds. It doesn't have to
succeed every time.

>Solving a problem means to me that
>the solution is somehow calculated
>or proofed. Thus I'm not very convinced
>by the idea of an oracled solution.

Again I think you are letting your intuition about what the words
"machine" and "solve" *ought* to mean confuse you. Oracles are not
intended to be implemented. They are hypothetical devices to let you
explore mathematically what you *could* solve *if* you had access to
an oracle.

>For the same reason I like the
>idea more of a NTM which is defined
>by a next move function which maps
>to a set of sates in contrast to a
>next move function of a DTM which
>maps on a single state (-tuple).

Yes, this is mathematically the same, and if you like this version better,
then by all means use it.

>But there the next move function has
>to "choose" one of the states and no
>one says (in a specific mathematical way)
>how the next state should or could be chosen?

*Any* next state can be chosen. The machine is said to "accept" the input
as long as *some* sequence of choices works. It is crucial that you look at
the definition of acceptance as well as the definition of the machine.

>Because polynomial
>time verification of an oracled solution isn't
>--- as I said --- persuasive to me yet.
>(According to the claim that an NTM *solves*
>problems like TSM in polynomial time)

It "solves" it only in a carefully specified mathematical sense. This says
nothing directly about how to solve the problem in real life.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Stephan Lukits on 13 Jan 2010 16:04
Stephan Lukits schrieb:
> tchow(a)lsa.umich.edu schrieb:
>> In article <hikik7$8c6$1(a)news-cedar.fernuni-hagen.de>,
>> Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>
> Thanks a lot for your detailed answer!
>
>>> What I don't understand is the guessing aspect.
>>> What if there are exponentially many structures
>>> S (as a function of input length)? What if the
>>> only right one of the exponentially many Structures
>>> is guessed last? Or is always first the right one
>>> guessed if there is one?
>>
>> [non-deterministic Turing machine is just an abstract concept]
>
> [NTM-models]

> [Doing TSM in polynomial Time]

> All which is
> left is to find the minimum of n integers.

Sorry, this is wrong. There are exponential
many integers :-(. I've to sleep over it.


best regards
Stephan
 |  Next  |  Last
Pages: 1 2 3 4
Prev: *** Evening Seminar by Prof Mike Hinchey, 28 Jan, UK: Evolving Critical Systems
Next: Algorithmic Random Oracle