Monthly Archives: October 2011

Class #7: Kolmogorov Complexity and Homomorphic Encryption

Does K(x), the Kolmogorov complexity of a string x, provide an objective, observer-independent 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 zero-knowledge proofs, probabilistically checkable proofs, (multi-prover) 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 Zero-Knowledge 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