Suppose we have an (efficient) NP-complete algorithm. I remind that proving a provable theorem isn’t an NP problem, because there are theorems whose shortest proof is of super-exponential length. However, finding a proof that is below a given “threshold” length is an…

read more

I have some error: from the below it follows that if the formal system found is distinct from the original one then it’s provable that the input algorithm does not halt (if it halts, it’s provable that it halts in Peano arithmetic)…

read more