Prev: Combsort: shrink factor for guaranteed O(n log n) worst case time?
Next: Incremental graph algorithms
From: Daniel Kraft on 6 Jun 2008 02:23
Hi,

consider a problem like finding a counter-example for Fermat's Last
Theorem (and just forget about Wiles' proof for some minutes...).
Obviously, given a quadrupel (a, b, c, n) one can easily (i.e.
polynomial in, for instance, log(a)*log(b)*log(c)*log(n) if I'm not
completely wrong) check if a^n+b^n=c^n, that is, if this is really a
counter-example.

So does this make finding a counter-example for FLT a problem in NP? On
the other hand, it's not even sure *if* there's such a counter-example
to find...

What if I knew there was such a quadrupel (a, b, c, n)? Then the
problem should clearly be in NP, should it? Maybe one could think of
log(a)*log(b)*log(c)*log(n) of this quadrupel as the input-size.

Does this mean the problem would be in NP if and only if there exists
such a counter-example? Or am I completely wrong here and problems like
that can fundamentally not be talked about "being in one or the other
complexity-class"?

Thanks,
Daniel

--
Done: Bar-Sam-Val-Wiz, Dwa-Elf-Hum-Orc, Cha-Law, Fem-Mal
Underway: Ran-Gno-Neu-Fem
To go: Arc-Cav-Hea-Kni-Mon-Pri-Rog-Tou
From: hbdere on 6 Jun 2008 04:07
On 6 Jun., 08:23, Daniel Kraft <d...(a)domob.eu> wrote:
> So does this make finding a counter-example for FLT a problem in NP? On
> the other hand, it's not even sure *if* there's such a counter-example
> to find...
Well, you should define the language first: FLTC = \{ n > 2 | there is
a counterexample to Fermats claim that a^n b^n != c^n for all a,b,c in
IN \}. As you discussed, that language is indeed in NP, as you can
define a TM that "guesses" the values for the counterexample (a,b,c; n
is the input) and verify them in polynomial time.

> What if I knew there was such a quadrupel (a, b, c, n)? Then the
> problem should clearly be in NP, should it?
Well, one quadruple would not help much. If you knew values (a,b,c)
for every n, then the language FLTC would be decideable in constant
time (always say "yes" if being asked if n is in FLTC), and hence be
in P, and hence be in NP.

> Does this mean the problem would be in NP if and only if there exists
> such a counter-example?
No. FLTC is in NP, as argued above. Given Wiles proof, it is also in
P, as he has shown that FLTC is actually the empty language.
Seems to me like you are confused by the fact that the TM checking for
counterexamples will always guess wrong. But that is no problem at
all; NP is defined that way. Of course, we can shortcut the whole
thing by using the knowledge that there is no counterexample to FLT,
but we do not have to.
This tells a nice story about the difficulties of proving that a TM
accepts the empty language (i.e., no word at all).

Likewise, the language of all numbers satisfying Goldbach's conjecture
is in NP: Guess two numbers, verify that they are prime, sum them up
and check the result. Now, is that language different from the natural
numbers?

> Or am I completely wrong here and problems like
> that can fundamentally not be talked about "being in one or the other
> complexity-class"?
Not at all.
From: Jym on 6 Jun 2008 04:11
On Fri, 06 Jun 2008 08:23:48 +0200, Daniel Kraft <d(a)domob.eu> wrote:

> Hi,
>
> consider a problem like finding a counter-example for Fermat's Last
> Theorem (and just forget about Wiles' proof for some minutes...).
> Obviously, given a quadrupel (a, b, c, n) one can easily (i.e.
> polynomial in, for instance, log(a)*log(b)*log(c)*log(n) if I'm not
> completely wrong) check if a^n+b^n=c^n, that is, if this is really a
> counter-example.
>
> So does this make finding a counter-example for FLT a problem in NP? On
> the other hand, it's not even sure *if* there's such a counter-example
> to find...
>
> What if I knew there was such a quadrupel (a, b, c, n)? Then the
> problem should clearly be in NP, should it? Maybe one could think of
> log(a)*log(b)*log(c)*log(n) of this quadrupel as the input-size.
>
> Does this mean the problem would be in NP if and only if there exists
> such a counter-example? Or am I completely wrong here and problems like
> that can fundamentally not be talked about "being in one or the other
> complexity-class"?

You're completely wrong. Well, not exactly :-D

The thing is that Fermat's Last Theorem, as well as many other "pretty
hard conjectures" don't depend on some parameters.

Classes of complexity are classes of problems depending on some inputs.
With FLT (or other), either the statement is true or is is false. Either
FLT is true, or it is false. Hence, it does not defines a problem in the
complexity theory sense of the term.

You should see complexity theory problems as functions from some input to
boolean.

If you consider the (obvious) problem one can associate to FLT, you'll
probably have something like that :
INPUT : 4 integers, a, b, c, n.
OUTPUT : YES if a^n+b^n=c^n, NO otherwise.

Obviously, this problem can be solved in polynomial time (as you pointed
out).

A slightly less obvious problem one can associate to FLT would be the
following :
INPUT : 3 integers a, b, c.
OUTPUT : YES if there exists n such that..., NO otherwise.

But now this problem is not in NP since there is absolutely no guarantee
that n is polynomially bounded by a, b and c or such.
[of course, Wiles' proof tells us that the problem is actually trivial,
but we forget about it for the moment.]

You have similar effect with many mathematical conjectures. As
conjectures, they are not problems (from the complexity theory point of
view) and it make no sense of trying to say they are P, NP, or even
undecidable. As problems, they usually don't really make sense.

--
Hypocoristiquement,
Jym.
From: Jym on 6 Jun 2008 04:31
On Fri, 06 Jun 2008 10:07:16 +0200, hbdere <hbdere(a)gmx.net> wrote:

> On 6 Jun., 08:23, Daniel Kraft <d...(a)domob.eu> wrote:
>> So does this make finding a counter-example for FLT a problem in NP? On
>> the other hand, it's not even sure *if* there's such a counter-example
>> to find...
> Well, you should define the language first: FLTC = \{ n > 2 | there is
> a counterexample to Fermats claim that a^n b^n != c^n for all a,b,c in
> IN \}. As you discussed, that language is indeed in NP, as you can
> define a TM that "guesses" the values for the counterexample (a,b,c; n
> is the input) and verify them in polynomial time.

Actually, this proves belonging to NP only if you first proove that a, b
and c are polynomially bounded by the input n (or size polynomailly
bounded by the size of the input). Something which I don't think you can
do [disregarding Wiles' proof, of course]. Or at least which require more
than handwaving to do.

> This tells a nice story about the difficulties of proving that a TM
> accepts the empty language (i.e., no word at all).

Which is clearly undecidable (hint : on input n, simulate program p for n
steps).

> Likewise, the language of all numbers satisfying Goldbach's conjecture
> is in NP: Guess two numbers, verify that they are prime, sum them up
> and check the result. Now, is that language different from the natural
> numbers?

What is the input of your problem ?

Languages in NP are existential languages in the sense that they have the
shape :
{ x / \exists y, P(x,y) } where P is checkable in polynomial time and y is
polynomially bounded by x (or |y| by |x|).

For FLT, either :
{ n / \exists, a, b, c, ...} (your choice) or {a, b, c / \exists n, ...}
(my choice in the other message)
have this shape, in both case, the property is checkable in polynomial
time, but in no case the witness is polynomially bounded by the input.

Now, what would you consider as a language for Goldbach's conjecture ?
{k / \exists p, p' primes, 2k=p+p'}
In this case, this defines a language in NP (if primality is in P (*)).

(*) can't remember this one... checking all the smaller numbers for
division requires an exponential number of division (in the size of the
number, since the size is log of the value)...

Goldbach's conjecture states that this "Goldbach language" is N (well,
integers larger than 2 to be precise).
If Goldbach was right, then "Goldbach language" is trivial (hence in P,
hence in NP).
If Goldbach was wrong, and there are only finitely many counter-examples,
then the language is also trivial.
If Goldbach was wrong, and there are infinitely many counter examples,
then the language is "really" NP and might be NP-complete.

So, basically, discussing the complexity of the language without knowing
the truth of the staement is a bit pointless. Moreover, the important and
interesting part in these classification is, imho, hardness proofs rather
than appartenance proofs. Indeed, most problems are in NP and prooving
that a problem is in NP is (almost) useless because it can still be P or
even LogSpace and easilly solvable. To show that something is not easy to
solve, you have to proove hardness. Prooving that a problem is NP-hard is
indeed interesting because you can forget about polynomial algorithms to
solve it [until someone proove P=NP, of course].

And obvisouly, since the problem might be trivial (depending on the truth
of the original conjecture), you can't proove hardness before solving the
conjecture...

--
Hypocoristiquement,
Jym.
From: hbdere on 6 Jun 2008 04:50
On 6 Jun., 10:31, Jym <Jean-Yves.Moyen+n...(a)ens-lyon.org> wrote:
> Actually, this proves belonging to NP only if you first proove that a, b
> and c are polynomially bounded by the input n (or size polynomailly
> bounded by the size of the input). Something which I don't think you can
> do [disregarding Wiles' proof, of course]. Or at least which require more
> than handwaving to do.
Yes, you are right about that. The remainder of your posting, however,
is obviously trying to tell me off for things you interpreted into my
statements (e.g. that I said something about decidability of language
equivalence, or about NP hardness); which is something I find a very
stupid thing to do. But I am too lazy now for arguing; it's friday,
after all.
 |  Next  |  Last
Pages: 1 2
Prev: Combsort: shrink factor for guaranteed O(n log n) worst case time?
Next: Incremental graph algorithms