Prev: *** Evening Seminar by Prof Mike Hinchey, 28 Jan, UK: Evolving Critical Systems
Next: Algorithmic Random Oracle
From: Stephan Lukits on 14 Jan 2010 03:44
tchow(a)lsa.umich.edu schrieb:
> In article <hilabm$m1q$1(a)news-cedar.fernuni-hagen.de>,
> Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:

Thanks again for your patience

>> 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.

O.k. we are getting closer. how do I konw that
it succeeds *in* time? How is the case
avoided that there are exponentially many
guesses, only one is right, which is guessed
and checked last. IMHO the question is not
if it succeeds since the problems investigated
are solvable. To me the question is how is
it done that it dose not not need exponential
time (which is as far as I understood the
important difference between NTMs and DTMS).
By definition?

>
>> 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.

Well, I don't have plans to develop
my on theory of NP-Completeness thus
I'll have to stick to the stuff
used by the gentlemen Garey and
Johnson which have done a great
job so far. And as far as I'm
informed Cook uses in his famous
paper also an oracle. Therefor
I really would like to understand
it.

best regards
Stephan
From: tchow on 14 Jan 2010 10:40
In article <himlgt$sg7$1(a)news-cedar.fernuni-hagen.de>,
Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>O.k. we are getting closer. how do I konw that
>it succeeds *in* time? How is the case
>avoided that there are exponentially many
>guesses, only one is right, which is guessed
>and checked last.

The machine is not *running through all possible guesses one at a time*.
It makes just *one* guess. As long as the time taken to make *one* guess
and check it is polynomial, it counts as a polynomial-time non-deterministic
machine.

A machine that makes just *one* guess does not "solve" the problem in the
real world. But we're not in the real world here. We're in the abstract
mathematical world where we can make up our own rules. We say that the
machine "accepts" the input if *some* guess is correct.

Let me emphasize: we are are NOT trying to solve the problem with the
machine! We are trying to *characterize* a class of problems. NP is
the class of languages accepted by a non-deterministic Turing machine.
It is *not* the class of problems *solvable* by them.

I repeat: we are are NOT trying to solve the problem with the machine!
--
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 14 Jan 2010 12:18
tchow(a)lsa.umich.edu schrieb:
> In article <himlgt$sg7$1(a)news-cedar.fernuni-hagen.de>,
> Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>> O.k. we are getting closer. how do I konw that
>> it succeeds *in* time? How is the case
>> avoided that there are exponentially many
>> guesses, only one is right, which is guessed
>> and checked last.
>
> The machine is not *running through all possible guesses one at a time*.
> It makes just *one* guess. As long as the time taken to make *one* guess
> and check it is polynomial, it counts as a polynomial-time non-deterministic
> machine.

O.K. thanks for your effort.

best regards
Stephan
From: Casey Hawthorne on 14 Jan 2010 17:05
On Thu, 14 Jan 2010 18:18:02 +0100, Stephan Lukits
<Stephan.Lukits(a)FernUni-Hagen.de> wrote:

>tchow(a)lsa.umich.edu schrieb:
>> In article <himlgt$sg7$1(a)news-cedar.fernuni-hagen.de>,
>> Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>>> O.k. we are getting closer. how do I konw that
>>> it succeeds *in* time? How is the case
>>> avoided that there are exponentially many
>>> guesses, only one is right, which is guessed
>>> and checked last.
>>
>> The machine is not *running through all possible guesses one at a time*.
>> It makes just *one* guess. As long as the time taken to make *one* guess
>> and check it is polynomial, it counts as a polynomial-time non-deterministic
>> machine.
>
>O.K. thanks for your effort.
>
>best regards
>Stephan

Did you understand what Tim was saying.

More people understanding what he said would go a long way to avoiding
more P!=NP "proofs".
--
Regards,
Casey
From: Stephan Lukits on 15 Jan 2010 03:10
Casey Hawthorne schrieb:
> On Thu, 14 Jan 2010 18:18:02 +0100, Stephan Lukits
> <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>
>> tchow(a)lsa.umich.edu schrieb:
>>> In article <himlgt$sg7$1(a)news-cedar.fernuni-hagen.de>,
>>> Stephan Lukits <Stephan.Lukits(a)FernUni-Hagen.de> wrote:
>>>> O.k. we are getting closer. how do I konw that
>>>> it succeeds *in* time? How is the case
>>>> avoided that there are exponentially many
>>>> guesses, only one is right, which is guessed
>>>> and checked last.
>>> The machine is not *running through all possible guesses one at a time*.
>>> It makes just *one* guess. As long as the time taken to make *one* guess
>>> and check it is polynomial, it counts as a polynomial-time non-deterministic
>>> machine.
>> O.K. thanks for your effort.
>>
>> best regards
>> Stephan
>
> 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)

> would go a long way to avoiding
> more P!=NP "proofs".

Is P = NP settled? This is new to
me. I thought most people suspect P!=NP?
Crancs like "the reals are countable"
should proof P=NP, shouldn't they?
I'm just a mathematician who wants to
learn to classify algorithms NP-complete
and understanding the basics for it.


Now you probably want to know what was IMHO
contradictory and wrong what Tim said, don't you?

"I repeat: we are are NOT trying to solve the problem with the machine!"

IMHO the whole thing is about defining a *complexity*
class. The notion of *complexity* directly depends on
effort for *solving* a problem. Thus you must have some
notion (if you like: abstract concept) of solving a problem.

But who am I you think. O.k. how about Michael R. Garey
and Davind S. Johnson in their book "Computers and Intractability"
(that's what I'm reading right now, therefor it's the context
in which I'm talking)

Page 13 bottom
Second, he [Cook] focused attention on the class
NP of decision problems that can be *solved* in
polynomial time by a nondeterministic computer.[...]

Page 28 bottom
A nondeterministic algorithm *"solves"* a decision
problem [...]

Page 29
A nodeterministic algorithm *solves* a decision problem
[...]

Page 29 below
The class NP is defined informally to be the class of
all decision problems \Pi that, under reasonable encoding
schemes, can be *solved* by polynomial time nondeterministic
algorithms.

I'm pretty sure that what Tim calls "acceptance" means the same
what Garey and Johnson intend if they say "solve". But if you
first built the notion of complexity on the effort *solving* a
problem, then it sounds not didactically wise to me, claiming
that a machine that is used defining a complexity class doesn't
solve any problem.

The next one is

"We're in the abstract mathematical world where
we can make up our own rules."

This tell teachers their children if they don't want
or not able to explain it right. And this statement
is not just completely wrong it also gives people who
don't know better a completely wrong picture of mathematics.

In mathematics we are bound to consistency at least.
If we cannot proof consistency like for ZFC, Peano-Arithmetic
or an axiomatic approach of the reals, we should have
at least one finite model (which we do for the mentioned
theories). A mathematical definition of a notion is done
within a framework consisting of (consistent) Axioms and
(at least "correct") rules of inference. A notion which
isn't defined axiomatically has to be defined on notions
which are already defined *and* the (mathematical)
existence of a mathematical object falling under the defined
notion must be *proofed*. If all this is the case *then*
we are in the world of mathematics. At least in mine world
of mathematics. But I don't have the impression that there
are a lot of mathematicians around who see it different.
And until now I'm not convinced, that an "oracle", "Guessing
module" or suchlike is in the/mine world of mathematics.

best regards
Stephan
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