Quote from: TPTB_need_war on December 15, 2015, 05:07:51 PM

Quote from: TPTB_need_war on December 15, 2015, 10:02:38 AM

I still believe there is some insight to gleem from the observation (conjecture or proven?) that converting deterministic intractable problems into tractable problems makes them nondeterministic and unbounded in entropy, but I am not seeing yet how to frame it in a way that proves anything. Perhaps proving that the conversion must be unbounded would prove P ≠ NP. I need to contemplate that.

On proving P ≠ NP, I do not understand why it can't be proven that the algorithmic Kolmogorov complexity of the "traveling salesman problem" is at least O(n²(2ⁿ-n-1)), i.e. an exponential lower bound, which is just below the O(n²2ⁿ) of Held-Karp algorithm which is the best known algorithm Huh

My logic is so simple, that I must be missing something.

Say I want to crack your 4 digit pin (0000-9999).

No matter what I do, I have to generate the numbers, try them, verify them.

Simply verifying the answer is just a subset of generating candidates/trying/verifying. So verification time alone is always less than trying candidates AND verifying.

Time spent (cracking + verifying) > (verifying), because verifying alone is (at least) -1 step.

So P ≠ NP.