> More pedantically, it’s possible for a polynomial solution to P=NP to exist without it running in polynomial time in python. That's not true. Any Turing mach

> More pedantically, it’s possible for a polynomial solution to P=NP to exist without it running in polynomial time in python. That's not true. Any Turing machine can be compiled into a Python program with at most cubic slowdown. More precisely, the number of Python bytecode operations executed will be at most quadratic in the running time p(n) of the TM, with all operation acting on a bounded number of objects of size O(log p(n)) (which for polynomial p() is just O(log n)). One can check Chapter 1 of Arora & Barak's Computational Complexity book for a description of the C/Java analogue of this claim, but it follows from a straightforward simulation argument: literally just hardcode the TM states and transition model, then execute it. The only bit to be careful about is addressing and address sizes growing unbounded, but the max size is only logarithmic in running time (simple proof, I believe this is an exercise in Sipser's book), and that's why we give ourself a cubic buffer.