If the decision versions of sets P and NP are not equal, then this implies the search versions of sets P and NP are not equal also. This is because if they were equal, we could use a polynomial algorithm for a search version of an NP-complete problem to solve the decision version of that NP-complete problem in polynomial time, and thus all problem in the decision version of NP are also in the decision version of P.
If the search versions of sets P and NP are not equal, then we get a lot of information about the time complexity of finding proofs that are easy to check as valid (e.g. most proofs mathematicians care about). In particular, there will be no general way of finding an easy-to-check-as-valid proof (of length N) of a statement in time polynomial in N, if the statement and corresponding proof encode an NP-complete problem and solution of some sort.
That is, “either there is no insight in mathematics in general, or the Church-Turing thesis is false, and humans are capable of crazy things.” (???)
??? Am I missing something?
If the decision versions of sets P and NP are not equal, then this implies the search versions of sets P and NP are not equal also. This is because if they were equal, we could use a polynomial algorithm for a search version of an NP-complete problem to solve the decision version of that NP-complete problem in polynomial time, and thus all problem in the decision version of NP are also in the decision version of P.
If the search versions of sets P and NP are not equal, then we get a lot of information about the time complexity of finding proofs that are easy to check as valid (e.g. most proofs mathematicians care about). In particular, there will be no general way of finding an easy-to-check-as-valid proof (of length N) of a statement in time polynomial in N, if the statement and corresponding proof encode an NP-complete problem and solution of some sort.
That is, “either there is no insight in mathematics in general, or the Church-Turing thesis is false, and humans are capable of crazy things.” (???)