[scythe]

>I believe that there's problems where it's difficult to even find a hard instance

Sure, but encoding the factorization of a large prime into 2-MAXSAT would necessarily imply constructing a hard instance of the latter. It follows that it isn't any more difficult to construct a hard instance of any NP-hard problem than it is to encode a more easily constructible problem into the same.

As for verifying the solution, that would be different, since it is not necessarily easy to verify the solution to a problem in OptP. I had not considered that part. But you probably don't have to go as far as importing integer factorization.

[kadoban]

> Sure, but encoding the factorization of a large prime into 2-MAXSAT would necessarily imply constructing a hard instance of the latter.

That should work if you pick something like one of the unsolved RSA challenges or something.

[FartyMcFarter]

The RSA challenges are very easy to generate - just generate large random numbers, check if they pass a primality test like Miller-Rabin (this doesn't take long even with a naive implementation). Then multiply two of those that do pass the test (distinct ones!), and you're done.

[kadoban]

Sure, but presumably they're difficult to solve. I'm saying that if they can _solve_ an unsolved one using this algorithm, that would certainly be compelling.

[FartyMcFarter]

Right - to elaborate, my point was that since:

1- it's easy to generate RSA-like challenges for factoring, a product of two large primes.

2- it's easy to turn these RSA-like challenges into instances of the SAT problem (the canonical NP-complete problem).

3- SAT problems can be reduced to any NP-complete problem.

4- these reductions are known, because the typical proof of NP-completeness is to provide a reduction from another NP-complete problem, which will ultimately end up with SAT if you follow the chain for long enough.

... it follows that it's not too hard to generate hard instances of any NP-complete problem, assuming that factoring itself is a hard problem.