Avi Wigderson School of Mathematics

Yüklə 412,5 Kb.
ölçüsü412,5 Kb.

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

  • Efficient Computation

  • 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


  • Axioms: self evident statements (eg 0 + 1 = 1 )

  • Deduction rules: simple, local (eg A, B  AB )

  • A proof of statement T is a sequence

  • 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.


  • Inputs: available data (eg bits, numbers,…)

  • Operations: simple, local (eg x,y  xy )

  • 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.

  • NP – problems for which solutions can be

  • 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 PNP

  • - Sources of new technologies: Quantum, DNA..

Probabilistic Algorithms

  • - Use independent, unbiased coin tosses 011101001111100100001…

  • - Perform task with very high probability

  • 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


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

Probabilistic Proof Systems

  • 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

  • assuming Factoring is HARD

  • 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


  • 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!

Yüklə 412,5 Kb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2023
rəhbərliyinə müraciət

    Ana səhifə