Data checking and verification
Randomization and coding
A guide to PCP, an approach towards
classification of NP problems

P versus NP
Have you heard about P vs NP problem?
• Millenium prize problems by Cray institutehttp://www.claymath.org/millennium/• P versus NP is not only million dollar problem,
Its value is trillion dollars.

Class P and class NP• Consider a computational problem M of input size n• P: class of polynomial time solvable problems in usualmodel of computation– M is in P if there is an algorithm to solve it in polynomialtime• Example: Sorting, Searching, Graph connectivity• Shortest path, text pattern matching• NP: class of polynomial time solvable problems in
nondeterministic model of computation– M is in NP if there is a nondeterministic algorithm to solve
it in polynomial time (difficult to understand, isn’t it?)• P is a subclass of NP

More intuitive description• Verification is often easier than solution– Solving an equation is more difficult than verification• NP: If we know the solution, we can show it suchthat verification is done in polynomial time
– 1: Hamilton path
– 2: Graph coloring,– 3: Does this SUDOK puzzle have a solution?

• A problem (probably) not in NP– 1: Will black win this Chess game ?
– 2: SOKOBAN game
– 3: #3SAT (number 3SAT)• Intuitively, a problem that we are convinced withcorrectness of solution easily if it is shown.

NP and co-NP• It is notable that negation of an NP problem
might not be in NP– Is a given graph G is colored by using k colors?
• We give the actual coloring to veryfy. Thus NP problem– Is a given graph G has no coloring with k colors?
• If so, how to convince it?

• Co-NP problem: negation of an NP problem• It is believed NP and co-NP are different• It might be true that NP ∩ coNP = P

P vs NP
• Is it true that verification is easier than solution ?
– Consider an equation f(x) = x5 - 3x4 +3x2 + 4 = 0– Ask “ is this equation has an integer solution less than n (say,n=100)”.
– Verification: f(2) = 32-48+12+4 = 0– Solution???

• P vs NP: Is there any problem where verification is easy (Ptime) but solution is difficult (not in P-time)?
• Philosophical question– Is it easy to learn than solve by yourself?
• Is it true that a difficult problem remains to be difficult even if you aresuggested a solution (you must make sure it is true).

– In real life, we must solve many NP problems(or even moredifficult problems). Human can solve them by training (likeSUDOK) for most of instances. Why??

Implication of P=NP
• If P=NP, we can solve many problems– Many-body problem in physics– Protein folding problem in biology– Optimal scheduling in manufacturing– Optimal traffic control– Many problems in computational chemistry• If P=NP, we have serious inconvenience– Current cryptology assumes P is not NP– Information security system is destroyed• Most of researchers believes P is not NP, and the above
situation only occurs in Scientific Fiction– But no one knows the truth• The biggest mathematical challenge in 21st century

Several approaches towards P vs NP
http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf
Lance Fortnow’s article• NP- complete theory (S.Cook and R.Karp)– Almost all NP problems are either in P or NP-complete( one ofthe most difficult problems in NP)• Circuit complexity– Show NP needs exponential size of circuits• Algebraic/group theoretic method– Relation to generalized Riemann hypothesis (Mulmuley)• From mathematical logic• Relation to randomness• Interactive Proof and Checkable Proof

Textbooks/papers• Randomized Algorithms (Motwani-Raghavan)• Efficient Checking of Polynomials and Proofs
and the Hardness of Approximation Problems(M. Sudan, ACM Distinguished Thesis, 1995)• Proof Verification and the Hardness ofApproximation Problems (S. Arora, C. Lund, R.
Motwani, M. Sudan, M. Szegedy), J. ACM, Vol45(3), 1998, pp. 501-555

Rajeev Motwani (from wikipedia)•••••

Motwani joined Stanford soon after U.C. Berkeley. Motwani was one of the co-authors (with LarryPage and Sergey Brin, and Terry Winograd) of an influential early paper on the PageRank algorithm,
the basis for Google's search techniques. He also co-authored another seminal search paper WhatCan You Do With A Web In Your Pocket with those same authors.[3]He was also an author of two widely-used theoretical computer science textbooks, RandomizedAlgorithms (Cambridge University Press 1995, ISBN 978-0521474658, with Prabhakar Raghavan)
and Introduction to Automata Theory, Languages, and Computation (2nd ed., Addison-Wesley, 2000,
with John Hopcroft and Jeffrey Ullman).
Prior to his involvement with Google, Motwani founded the Mining Data at Stanford project (MIDAS),an umbrella organization for several groups looking into new and innovative data management
concepts. His research included data privacy, web search, robotics, and computational drug design.
He was an avid angel investor and had funded a number of successful startups to emerge fromStanford. He sat on the boards of Google, Kaboodle, Mimosa Systems, Adchemy, Baynote, Vuclip,
NeoPath Networks (acquired by Cisco Systems in 2007), Tapulous and Stanford Student
Enterprises among others. He was also active in the Business Association of Stanford Entrepeneurial
Students (BASES).[4][5][6]He was a winner of the Gödel Prize in 2001 for his work on the PCP theorem and its applications
to hardness of approximation.[7][8]Verification
Algebraic methods to verify
information

Verification in real life
• Given two data A and B, we want to verify A=B– We want to do it without reading A and B explicitly• If A and B are “persons”– How we can “read” data of persons completely?
• Impossible!

– Name, blood type, color of hair/eye,……
– ID numbers, secret keywords,– Finger print, DNA identification• If A and B are twins………

Fingerprinting• We recall the data checking problem we
discussed some weeks ago– Given a set of n data {a(1),a(2),…,a(n)}, and wesuspect one (or more) data is modified.
– How should we check efficiently?
• The sum of all data
• Use hash function, and sum of h(a(i))– This is an example of “fingerprint”

Fingerprinting for matrix multiplication• Consider a prime p• Given n by n matrices A, B, and C, we want toverify AB = C mod p– Computation in the field GF(p) (or Zp )• Can you do it in O(n2) time?

Verifying an identity• X = (x1,x2,..,xd)• We want to verify a polynomial identity
F1(X)=F2(X) of degree nVerifying an identity• X = (x1,x2,..,xd)• We want to verify a polynomial identity
F1(X)=F2(X) of degree n– Or more cruel identities

Verifying strings (communicationcomplexity)• Alice and Bob have very long documents Aand B (of length n each).
• They want to confirm they are identical.
– They speak on wire, and cannot tell the whole
document.

• How is your solution?
– Assume that they have a program to generate alarge prime number.

Pattern matching via verification• Given a text T of length n (bit string)• For each query pattern P of length m, we wantto find location of occurrence of P in T
• Both m and n are long (say, m = 100000, n =10000000)• KMP algorithm, BM algorithm: optimalO(n+m), but not much practical• Can we apply verification idea?