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

jeffrey_h_miller@xxxxxxxxx wrote:
>
> Googmeister wrote:
>> jeffrey_h_miller@xxxxxxxxx wrote:
>> > Jaisingh Solanki provided this problem in a different thread. I think
>> > it would fit the bill and can be modified to be solvable too (I think).
>> >
>> > 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
>>
>> Interesting. What's the complexity of this problem? Has it been
>> proven to be outside of NP?
>
> 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)?

So why is this a justification for it being outside NP?

Or am I thinking about this wrong?

NG
--
"The life of a repoman is always intense."
.

Relevant Pages