34.2 Polynomial time verification
Document last modified: 

Algorithm's that verify membership in a language

x - a problem instance (input string)

y - a certificate (solution string)

A - an algorithm, verifies x if there exists a certificate y such that A(x, y)=1

Language verified by A is:

L = {x ∈ {0, 1}* : ∃ certificate y ∈ {0, 1}* such that A(x, y) = 1}

 

Algorithm A verifies language L if for any string x ∈ L, there is a certificate y that A can use to prove that x ∈ L.

For any string, x ⊆ L, there is no certificate proving that x ∈ L.

 

Example: Hamiltonian graph cycle (HAM-CYCLE) is a simple cycle that contains each vertex.

The certificate is the list of vertices in the Hamiltonian graph cycle, enough information for verification

(e.g. vertices <1, 2, 3, 4, 5>)

If not Hamiltonian, there is no list that can fool the verification algorithm.

Algorithm A would not be fooled by <2, 1, 3, 4, 5>

L is just those input strings of vertices which are a Hamiltonian cycle.

{<1, 2, 3, 4, 5>, <2, 3, 4, 5, 1>, ..., <5, 4, 3, 2, 1>, ...}

Example:

For one instance of HAM-CYCLEL where:

V= {1,2,3,4,5}

E = {(1,2),(2,1),(1,5),(5,1),...}

G = (V,  E)

AHAM-CYCLE( G, <1, 2, 3, 4, 5>) = 1

AHAM-CYCLE( G, <1, 2>) does not equal 1

 

 

Complexity class NP - Nondeterministic Polynomial time

A class of languages that can be verified by a polynomial-time algorithm.

L ∈ NP iff ∃ a 2-input polynomial-time algorithm A and constant c such that:

L = {x ∈ {0, 1}* : ∃ a certificate y with |y| = O (|x|c) such that A(x, y) = 1}

x is the instance (input) and y is the solution to be verified

Algorithm A verifies L in polynomial time

Example: Proving PATHL ∈ NP

PATH problem:

xi = (G, u, v, k), where

  • G is the graph,
  • u is the source vertex,
  • v is the target vertex,
  • k is an integer specifying the maximum allowable length of a path from u to v.

Given PATH problem instance:

x1 = (G, r, y, 5),

certificate p = < r, s, w, x, y >

use APATH (x1, p) to verify that path p's length is ≤ k

APATH (x, p) verifies p is a path in x's G of length k or less in polynomial time by:

APATH(x, p) verifies PATHL as follows:

  1. Verify x is a proper encoding of <G,u,v,k>
  2. Verify each v ∈ p is unique, i.e. p is a set.
  3. Verifies first vertex in list is: u ∈ x.
  4. Verifies last vertex in list is: v ∈ x.
  5. Verify length[p] ≤ k
  6. for i ← 1 to length[p]-1 do verify (vi, vi+1) ∈ E[G]
  7. If steps 1-6 verify, APATH (x, p) = 1

Therefore PATHL ∈ NP, since APATH(x, p) can produce either a 0 or a 1 in polynomial time.

But we already knew that PATH ∈ P, and P ∈ NP, i.e., anything that can be computed in polynomial time can be verified in polynomial time.

 

Question: Are there problems where no known polynomial time algorithm exists to compute the solution, but a solution can be verified in polynomial time? 

Yes, HAM-CYCLE ∈ NP, but no known polynomial time algorithm exists to decide HAM-CYCLE.

Give another.