denis_berthier wrote:blue wrote:If it could be shown that not-necessarily-minimal instances of the "pattern", could be verified in polynomial time in the puzzle size, it would follow that (P = NP).

If it could be shown that minimal instances of the "pattern" ("his patterns"), could be verified in polynomial time in the puzzle size, it would follow that (Co-NP = NP).

Yes, but... would you engage in such an adventure?

I would not. A minimal instance is very much like a "minimal unsatisfiable core" for an unsatisfiable SAT problem, and there's no low hanging fruit on that tree.

denis_berthier wrote:BTW, the conjecture is not P = NP, but P <> NP. From a formal POV, it may seem to be the same thing. But, in practice, a vast majority of people dealing with it believe that NP <> P. [OK, maths isn't a matter of polling].

Right, the prevailing view is that (P = NP) is false.

denis_berthier wrote:As for proving P<>NP, it's a lifetime job and I'll keep it for some future life if any - but not the next, nor even the second next; there are so many other things I'd like to do before! Indeed, if I had to work on this, what'd I'd probably try to prove is not P<>NP, but that it is undecidable.

I'll admit to spending a few days each year, thinking about what it would take to prove it false, and what "dead ends" in such attempts, might imply about it's decidability.

If I had to make a correct guess to save my life, I would hope that "it's either false or undecidable" is an available option.

I'ld be quite distressed, if I had to choose between false and undecidable.

With eternal bliss and instant death as the possible outcomes, I still wouldn't jump at a chance to choose between "true" and "false or undecidable".

Regards,

Blue.