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


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.

.

Relevant Pages