If so, then P=NP implies a polynomial-time procedure where first you nail down a possible length, then you find
characters one by one.
Yup! Even the decision version of the P vs NP question is certainly about search, for this reason (contrary to what the grand parent is claiming). One can generally solve optimization problems via a decision algorithm by paying at most a polynomial cost, precisely as you suggested.
I seem to remember that Levin’s work was about the optimization version of P vs NP, and Cook’s work was about the decision version. They are both given credit these days.
This is only true if P=NP, which is very unlikely! If P=/=NP, the far more likely scenario, then we get no new information about the time complexity of search.
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.” (???)
Yup! Even the decision version of the P vs NP question is certainly about search, for this reason (contrary to what the grand parent is claiming). One can generally solve optimization problems via a decision algorithm by paying at most a polynomial cost, precisely as you suggested.
I seem to remember that Levin’s work was about the optimization version of P vs NP, and Cook’s work was about the decision version. They are both given credit these days.
This is only true if P=NP, which is very unlikely! If P=/=NP, the far more likely scenario, then we get no new information about the time complexity of search.
??? 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.” (???)