===========================================================================
CSC 363H                Lecture Summary for Week  8             Summer 2007
===========================================================================

-----------
The class P
-----------

Complexity class TIME(t(n)), for some function t : N -> R+:

    TIME(t(n)) = { L | L is a language decided by some TM that runs
                        in worst-case time O(t(n)) }

For example, TIME(n^2) contains every language decided by a TM in
worst-case time O(n^2).

Concentrate on "coarse scale": ignore polynomial differences.  Not that
they are unimportant, but that larger differences must be addressed first.

"Tractability thesis":
all reasonable deterministic models are polynomially equivalent (i.e., can
simulate one another with at most a polynomial factor loss of efficiency).

P = U_k TIME(n^k), i.e., language L belongs to P iff L can be decided by
some deterministic algorithm (TM or otherwise) in worst-case polytime.

Importance:
 -  Robust: does not depend on details of model, as long as it is
    deterministic.
 -  Useful: captures rough notion of efficiency.

Conventions:
 -  Describe computation in stages, where each stage is "obviously"
    computable in polytime (with justification) and at most polynomially
    many stages are executed, on any input.
 -  Encodings: "reasonable" now means "can be encoded/decoded in polytime".
    In particular, numbers must be represented in some base >= 2 (unary
    notation requires k symbols to represent integer k, exponentially worse
    than the log_b(k) symbols required in base b).
 -  read more about encoding conventions in section 7.2, pp258-259.

Examples:  Almost all algorithms you've seen in other courses.

Example: RELPRIME = { <x,y> : x and y are relatively prime } is in P
in book: Thm 7.15

Example: PATH = { <G,s,t> : G is a graph that contains a path s to t } is in P
in book: Thm 7.14

------------
The class NP
------------

We've seen that nondeterminism is not "practical".  Why use it, then?

Because a large number of real-life problems have no known efficient
solution (i.e., are not known to belong to P), yet can be solved
efficiently using nondeterminism.  So nondeterminism allows us to
characterize a large class of problems.  Also, nondeterminism is an elegant
way to add (what seems to be) significant power to the model.

NTIME(t(n)) =
    { L : L is a language decided by a NTM in worst-case time O(t(n)) }
NP = U_k NTIME(n^k)
   = { L : L is decided by some polytime NTM }

By tractability thesis, NP independent of specific details of
nondeterministic model (as long as it's nondeterministic).

Definition: A verifier V for a language L is a deterministic algorithm
that takes inputs of the form <x,c> and satisfies the following condition:
    forall x, [ x in L <=> ( exists c s.t. V accepts <x,c> )

Think of c as being a "certificate" that convinces you that x is in L,
and think of V as the algorithm that checks if a given certificate is valid.
So: IF x is in L, THERE EXISTS a certificate c for x that convinces V
IF x is not in L, FOR ALL certificates c for x, c does not convince V

Note: The running time of a verifier is always measured as a function
of the length of x only (i.e. not including c). Think of what happens
if we measure the running time as a function of c.

Theorem:
    NP = { L : L has a polytime verifier }
in book: Thm 7.20.

Examples:

 -  HAMPATH = { <G> : G is an undirected graph that contains a Hamiltonian
    path, i.e., a path that includes every vertex exactly once }
    HAMPATH in P?  Unknown (checking all possible paths not polytime.)
    HAMPATH in NP?  Yes:
        On input <G,c>:
         1. Check c encodes a list of vertices (v_1,v_2,...,v_n).
         2. Check c contains every vertex of G exactly once, i.e.,
            V = {v_1,v_2,...,v_n}.
         3. Check G contains every edge between successive vertices in c:
            (v_1,v_2) in E, (v_2,v_3) in E, ..., (v_{n-1},v_n) in E.
         4. Accept if all checks succeed; reject if any fail.
    By definition of the language, if G in HAMPATH, then verifier accepts
    <G,c> for some value of c (a Hamiltonian path in G); if G not in
    HAMPATH, then verifier rejects <G,c> for all values of c.  Moreover,
    verifier runs in polytime: if G contains n vertices and m edges,
    runtime is at most O(n^2 m).