|
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 Church-Turing 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?) Bug-free 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 ? NP-complete – 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 [Blum-Micali-Yao, Nisan-Impagliazzo-Wigderson] Assuming (something like) “P≠NP” ! Hard problems Pseudo-random 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 Zero-knowledge proofs Poker on the telephone E-commerce 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 3-colorable” 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 [Arora-Safra, Arora-Lund-Motwani-Sudan-Szegedy]: Every proof can be efficiently transformed to a PCP Refereeing (even by amateurs) in a jiffy! Major application – approximation algorithms
Zero-Knowledge (ZK) proofs [Goldwasser-Micali-Rackoff] claim: The Riemann Hypothesis Prover: (argument) Verifier: (editor/referee/amateur) Prover’s concern: Will Verifier publish first? ZK proofs: argument reveals only correctness! Theorem [Goldreich-Micali-Wigderson]: 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? zero-sum games: YES [von Neumann 1928] Reasonable theory? YES: computing it is in P strategic games: YES [Nash 1950] Reasonable theory? NO: PPAD-complete 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 - Fault-tolerance - Small-world phenomena Every natural theory must be efficient! P vs NP captures how much we can know!
Dostları ilə paylaş: |
|
|