>>11571612Because if it is PROVEN to be hard to solve and PROVEN to be easy to check, you've shown P =/= NP.
The point of p vs np right now is that we dont actually have proofs of the difficulty of the problems, we just cant find a reduction of the algorithms down to the lower complexity class. Let's take cryptography - It's NOT actualy proven that cracking some complex cypher is not poly time, what happens is some mathematician comes up with a way to encrypt data and publishes it and goes "hey guys I can't figure out a way to make this simpler, the best reduction I've found is like 4^n, can you guys do better?" and then a bunch of other mathematicians try, and no one succeeds, so they go "yea this works as an encryption".
There is no PROOF that the encryption is actually not-reducible below 4^n, it's jsut no one has found a better way to do it. That's basically the state of the whole field right now.
What you're asking for, that "the problem has been PROVEN to be hard to solve but easy to check" is basically asking for the proof of the existence of a one way function, which would prove P != NP.
