
Avi Wigderson School of Mathematics

tarix  01.08.2018  ölçüsü  412,5 Kb.   #60072 

Proof, Computation, & Randomness Kurt Gödel John von Neumann and Theoretical Computer Science Avi Wigderson School of Mathematics Institute for Advanced Study
Fundamental concepts: Proof vs. Truth Gödel’s Incompleteness Theorem Computation and its limitations, computation in nature Gödel’s letter, and the P vs. NP problem Limits of Knowledge Randomness: Probabilistic algorithms, pseudorandomness, weak random sources Cryptography: Secrets Probabilistic Proofs Game Strategy, Rationality, Through computational complexity glasses
Proof Axioms: self evident statements (eg 0 + 1 = 1 ) Deduction rules: simple, local (eg A, B AB ) A1, A2, …,Ak, Ak+1…., Ai, …, An=T, such that A1, A2, …., Ak are axioms Each subsequent Ai is derived from two previous statements by a deduction rule. Truth of axioms implies truth of T Verification: fast&simple mechanical procedure.
Computation Inputs: available data (eg bits, numbers,…) Operations: simple, local (eg x,y xy ) A computation of a function f is a sequence x1, x2, …,xk, xk+1 …., xi, …, xn=f(x1,…,xk), s.t. x1, x2, …,xk are inputs Each xi is computed from two previously computed values by a basic operation A finite program specifies which op to apply next
Computation is everywhere ChurchTuring Thesis: “Turing machine captures every realistic physical model of computation” Computation: evolution of an environment via repeated application of simple, local rules [von Neumann’s cellular automata] (Almost) all Physics and Biology theories satisfy! Weather  Proteins in a cell Magnetization Ant hills  Fission  Epidemics Brain  Populations  Burning fire Nature provides ideas/technologies for computing Understanding algorithms is essential to science.
Computation vs. Proof Common feature: Simple, local steps Can every true statement be proven? Gödel’s Incompleteness Theorem [1931]: Some true statements are unprovable! Can every function be computed? Turing’s Undecidability Theorem [1936]: Some functions are not computable! Proof: f(T) = 1 if statement T is true. f(T) = 0 if T is false. A program for f is a complete proof system #
Limits of Knowledge (I) Undecidable Problems Example of input Diophantine equations ( integer solutions?) Bugfree programs (Does P0 always halt?) Infection (will it die out?)
Limits of Knowledge (II) Decidable: Solvable in finite time. Which problems are efficiently solvable? [’60s Cobham, Edmonds, Rabin] Efficient:Time grows moderately with data size. P – problems which can be solved efficiently [’70s Cook, Levin, Karp] NP – problems which can be verified efficiently
Efficient Computation & P vs. NP Gödel’s letter to von Neumann [1954]: Theorem f(T,n)=1 if T has a proof of length n Proving f(T,n)=0 otherwise. This problem is decidable! Is it tractable?? Algorithm for f: Try all possible sequences of length n; for each, check (easy) if it proves T. Time complexity: >2n steps (terribly inefficient) Is there an efficient algorithm (n or n2 steps)? Can one avoid “brute force” search, when efficient verification exists? This is the P vs. NP question – central to Math & Science!
Limits of Knowledge (II) P – problems for which solutions can be efficiently found. Everything we can know. easily verified. Everything we want to know. Mathematician: Given a statement, find a proof Scientist: Given data on some phenomena, find a theory explaining it. Engineer: Given constraints (size,weight,energy), find a design (bridge, medicine, phone) All expect to know when they succeeded!
Does P=NP ? NPcomplete – Hardest problems in NP 1000’s of them across the sciences. Math Is a given knot is unknotted? CS Can we satisfy a set of constraints? Biology Find the shape of protein folding Physics Determining min energy All equally difficult! If any is easy: P=NP.  Strong evidence that PNP  Sources of new technologies: Quantum, DNA..
Probabilistic Algorithms  Use independent, unbiased coin tosses 011101001111100100001… Are probabilistic algorithms much faster than deterministic ones? YES: Examples all over CS, Statistical Physics, Math, Biology, Operations Research, Economics… No: Theorem [BlumMicaliYao, NisanImpagliazzoWigderson] Assuming (something like) “P≠NP” ! Hard problems Pseudorandom generators
Randomness
Unreasonable usefulness of hard problems  Cryptography Assumption: Factoring Integers has no efficient algorithm (assumption implies P NP) Secret communication Digital signatures Electronic cash Zeroknowledge proofs Poker on the telephone Ecommerce Everything!
The Millionaires’ Problem
Is a mathematical statement claim true? E.g. claim: “No integers x, y, z, n>2 satisfy xn +yn = zn “ claim: “The map of Africa is 3colorable” An efficient Verifier V(claim, argument) satisfies: *) If claim is true then V(claim, argument) = TRUE for some argument (in which case claim=theorem, argument=proof) **) If claim is false then V(claim, argument) = FALSE for every argument
Probabilistically Checkable Proofs (PCPs) claim: The Riemann Hypothesis Prover: (argument) Verifier: (editor/referee/amateur) Verifier’s concern: Is the argument correct? PCPs: Verifier reads 100 (random) bits of the argument. Thm [AroraSafra, AroraLundMotwaniSudanSzegedy]: Every proof can be efficiently transformed to a PCP Refereeing (even by amateurs) in a jiffy! Major application – approximation algorithms
ZeroKnowledge (ZK) proofs [GoldwasserMicaliRackoff] claim: The Riemann Hypothesis Prover: (argument) Verifier: (editor/referee/amateur) Prover’s concern: Will Verifier publish first? ZK proofs: argument reveals only correctness! Theorem [GoldreichMicaliWigderson]: Every proof can be efficiently transformed to ZK proof Major application  cryptography
Game Theory von Neumann 1928: The minimax Theorem von Neumann & Morgenstern 1944: Game Theory Make conflicts in Economics, Politics, War & life, amenable to mathematical analysis Is there always a rational solution to conflicts? zerosum games: YES [von Neumann 1928] Reasonable theory? YES: computing it is in P strategic games: YES [Nash 1950] Reasonable theory? NO: PPADcomplete Algorithmic Game Theory Agents: efficient algs
Conclusions Efficient computation: A lens through which basic notions get new meaning:  Proof  Game / Strategy  Randomness  Secret / Privacy  Learning  Knowledge  Faulttolerance  Smallworld phenomena Every natural theory must be efficient! P vs NP captures how much we can know!
Dostları ilə paylaş: 

