Re: Can someone give me an example of this type of problem?

In article <dlgd01013i@xxxxxxxxxxxxxxxxx>,
Nathan Gilbert <nathan.gilbert@xxxxxxxxx> wrote:
>jeffrey_h_miller@xxxxxxxxx wrote:
>>> jeffrey_h_miller@xxxxxxxxx wrote:
>>>
>>> > Problem: Input is u, v, and w (three natural numbers) and the problem
>>> > is to check if there exist natural numbers x, y, and z such that
>>> > x^u + y^v = z^w
>>
>> Since the witness (u, v, w) can get arbitrarily large, I think it's
>> outside NP.
>
>The number of cities in the Traveling Salesman problem can also get
>arbitrarily large, yet it is in NP (NP-HARD actually)?

First of all, I think he meant to say "the witness (x, y, z)" rather than
"the witness (u, v, w)." The issue is not that the size of the instances
can get arbitrarily large, but that the size of the witness is arbitrarily
large.

For most problems in NP that arise in practice, it is easy to prove that
they are in NP, using the definition of NP as those problems for which there
exist a short certificate. That is, there exists a polynomial-time Turing
machine M such that for any positive instance, there exists a "witness" or
"certificate" whose size is polynomial in the size of the instance, and
which M can examine to confirm that the instance really is a positive
instance, and such that for any negative instance, no alleged certificate
can fool M. For the traveling salesman problem, simply exhibit a tour;
that's your witness.

The "obvious" way to witness in this case is to exhibit the solution
(x, y, z). Unfortunately, the difficulty here is that there is no
guarantee that this certificate is "short"; perhaps the lengths of the
smallest x, y, and z are exponential in the lengths of u, v, and w.
Therefore this type of certificate (apparently) does not work.

However, all this shows is that this method of trying to prove that the
problem is in NP fails. It does not prove that the problem is not in NP.
There might be some other very complicated but short certificate that
works.
--
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
.