
Recent Posts
Recent Comments
Archives
Categories
Meta
Monthly Archives: October 2011
Class #7: Kolmogorov Complexity and Homomorphic Encryption
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
Posted in Uncategorized
40 Comments
Class #6: Proof Protocols, Semantics of Computations, and Waterfalls
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
Posted in Uncategorized
19 Comments
Class #5: Knowledge Representation, Analytic vs. Synthetic, and ZeroKnowledge Proofs
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
Posted in Uncategorized
28 Comments
Class #4: The P vs. NP Problem, Human Mathematical Creativity, and Knowledge of Numbers
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
Posted in Uncategorized
50 Comments