
Recent Posts
Recent Comments
Archives
Categories
Meta
Advertisements
Does K(x), the Kolmogorov complexity of a string x, provide an objective, observerindependent notion of the “amount of patternlessness” in x? Or is the notion circular, because of the “additive constant problem”? Do some choices of universal programming language yield … Continue reading
In class, someone suggested why traditional mathematical proofs seem to differ from zeroknowledge proofs, probabilistically checkable proofs, (multiprover) interactive proofs, quantum proofs, and all the other exotic types of proof studied in modern cryptography and complexity theory. Namely, with a … Continue reading
Which is the more fundamental concept: “knowing how” or “knowing that”? Is it possible to “know” that 37×43=1591, yet not “know” the prime factors of 1591? If so, what is the thing that you know in the one case but not … Continue reading
Would a proof of P=NP have philosophical implications? If so, what? Does it make sense to discuss “HumanP,” loosely defined as the class of decision problems solvable in polynomial time by human beings? Is “HumanP” meaningless because we can’t give … Continue reading