Prev: *** Evening Seminar by Prof Mike Hinchey, 28 Jan, UK: Evolving Critical Systems
Next: Algorithmic Random Oracle
From: RussellE on 15 Jan 2010 03:39
On Jan 13, 5:42 am, Stephan Lukits <Stephan.Luk...(a)FernUni-Hagen.de>
wrote:
> 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)?

Doesn't matter.
You can think of a NTM as exponential size set of TM's.

>  What if the
> only right one of the exponentially many Structures
> is guessed last?

There is no last. We assume each TM in the NTM
is checking one guess. What matters is that each
TM halts after a polynomial number of steps.

This is an existence proof. It tells us there exists a DTM
that could have solved the problem in a polynomial number
of steps if the DTM had started with the right guess.

From this, and the definition above, we can prove
a problem is in NP if there exists a DTM that can verify
a possible solution in a polynomial number of steps.

> Or is always first the right one
> guessed if there is one?

There may not be a right one. The problem could be
unsolvable. Even so, every TM will halt after a
polynomial number of steps. So, a NTM can
determine the problem is unsolvable in a
polynomial number of steps.

Later on you ask about oracles.
Oracles are how the DTM's makes the right guess.
You can think of an oracle as a cheat sheet, like
a textbook with all the problems already solved.
We don't really care how the oracle guesses the
right answer, we just assume it can.

There are real life examples of "oracles".
Most chess playing programs have an "opening book".
When you make a move in the opening,
the program doesn't try to calculate the best response.
Computing the best move could take an exponential
number of operations. Instead, the program will look
up the current position in a database. The database,.
or opening book, tells the program what move to make.
Looking something up in the opening book only
takes a polynomial number of steps.

Opening books are often compilations of
chess games played by grand masters.

Of course, the progam will eventually be in a position
not in the opening book and it will have to actually compute
the best move.

We assume oracles always have the right answer.


Russell
- 2 many 2 count
From: Stephan Lukits on 15 Jan 2010 03:57
RussellE schrieb:
> On Jan 13, 5:42 am, Stephan Lukits <Stephan.Luk...(a)FernUni-Hagen.de>
> wrote:

Thanks for your detailed answer.

>> What if there are exponentially many structures
>> S (as a function of input length)?
>
> Doesn't matter.
> You can think of a NTM as exponential size set of TM's.

O.k. I got that one.

>
>> What if the
>> only right one of the exponentially many Structures
>> is guessed last?
>
> There is no last. We assume each TM in the NTM
> is checking one guess. What matters is that each
> TM halts after a polynomial number of steps.

O.k. We think of an NTM as exponential size set
of TM's which all work parallel. I got that one
too and it is sound to me.

>
> This is an existence proof. It tells us there exists a DTM
> that could have solved the problem in a polynomial number
> of steps if the DTM had started with the right guess.

Yes. (*)

>
> From this, and the definition above, we can prove
> a problem is in NP if there exists a DTM that can verify
> a possible solution in a polynomial number of steps.

Yes.

>
>> [...]
> [...]
> Later on you ask about oracles.
> Oracles are how the DTM's makes the right guess.
> You can think of an oracle as a cheat sheet, like
> a textbook with all the problems already solved.

But before I'm allowed to use an oracle for a
problem I have to proof its existence with the
methods from (*)? Or I have to show IMHO, that
an oracle is equivalent to an NTM?

> [...]

--
Gruß, Stephan

Wer das erste Knopfloch verfehlt,
kommt mit dem Zuknöpfen nicht zurande (Goethe)
From: tchow on 15 Jan 2010 10:53
In article <hip7t5$63u$1(a)news-cedar.fernuni-hagen.de>,
Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>"I repeat: we are are NOT trying to solve the problem with the machine!"

I was using "solve" in the sense that *you* seem to be using it, not in
the way that the literature uses it. That is the source of the confusion.

For you, "solving" a problem is intimately tied to *implementation*. Thus
you cannot imagine saying that a non-deterministic machine "solves" a
problem unless you can envisage translating the machine into a real-world
implementation that is stuck doing things one step at a time.

Non-deterministic machines do not "solve" problems in this sense. It is
better to say that they "accept" an input if some guess is correct.

Once one understands this, then it can be suggestive to use the term
"solve" to describe what the non-deterministic machine is doing, and
that is what the literature tends to do. It has the unfortunate effect
of confusing beginners like you, of course.
--
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: cplxphil on 15 Jan 2010 14:34

> > Did you understand what Tim was saying.
>
> Well, most of what he said sounds like
> a mantra which he is repeating since
> several years.  Since IMHO contradictions
> and simply wrong statements in this mantra
> I didn't saw a point keeping discussing
> and wasting his time and mine.  (In his
> understanding of the subject he is probably
> not contradictory: If I new what the notions
> he uses mean to him, I probably would understand
> but it seems to much effort to me figure this out.)
>
>
>
> > More people understanding what he said
>
> Maybe people don't understand because what
> he says is partly contradictory and wrong.
> (and maybe they don't have the skills to
>   recognize it)
>

I haven't been following this thread closely enough to be able to try
to address any of your concerns, but I thought I would mention to you
that it's unlikely that Tim Chow is contradictory or wrong. It's
possible that he doesn't understand exactly what the source of your
confusion is, but Tim is: 1) extremely knowledgeable, 2) one of the
most helpful people on comp.theory (and the most helpful to me
personally) , and 3) basically never wrong. I've learned a lot from
his answers to some of my often basic questions, and you probably
would too if you gave his responses careful study with an open mind
rather than dismissing them as contradictory.

-Phil
From: RussellE on 16 Jan 2010 05:16
On Jan 15, 12:57 am, Stephan Lukits <Stephan.Luk...(a)FernUni-Hagen.de>
wrote:
> RussellE schrieb:

> > Later on you ask about oracles.
> > Oracles are how the DTM's makes the right guess.
> > You can think of an oracle as a cheat sheet, like
> > a textbook with all the problems already solved.
>
> But before I'm allowed to use an oracle for a
> problem I have to proof its existence with the
> methods from (*)?

You can just assume such an oracle exists.

>  Or I have to show IMHO, that
> an oracle is equivalent to an NTM?

Now, you are asking about the strength of
the oracle. I don't know much about oracles.
Tim might be able to tell you more about
different types of oracles.


Russell
- 2 many 2 count
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: *** Evening Seminar by Prof Mike Hinchey, 28 Jan, UK: Evolving Critical Systems
Next: Algorithmic Random Oracle