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

Examples:

 -  COMPOSITES = { x : x is a composite number }
    COMPOSITES in P?  Unknown (checking all possible factors not polytime.)
    COMPOSITES in NP?  Yes:
        On input <x,c>:
         1. Check that 1 < c < x.
         2. Check that c divides x evenly.
         3. Accept if all checks succeed; reject if any fail.
    If x is composite, then the verifier will accept <x,c> when c is a
    factor of x.  If x is prime, then the verifier will reject <x,c> for
    all values of c.
    Moreover, the verifier runs in polytime:
    comparing integers (1 < c < x) can be done in linear time;
    dividing integers can be done in quadratic time.

-----------
P, NP, coNP
-----------

 -  HAMPATH^C, CLIQUE^C, SUBSET-SUM^C don't appear to belong to NP:
    apparently, no way to give a short certificate of NON-membership in
    HAMPATH, CLIQUE, or SUBSET-SUM.

 -  On the other hand, COMPOSITES^C = PRIMES can be shown to belong to NP
    (using number theory).  In fact, recent research result (Agrawal,
    Kayal, Saxena 2002) showed that PRIMES is actually in P (for more
    details, see http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html).

Definition: coNP = { L^C | L in NP } = { complements of languages in NP }.
Note: coNP =/= NP^C!  L in coNP iff L^C in NP but L in NP^C iff L notin NP.

[Picture: P subset of NP intersect coNP, all subset of decidable;
analogy with computability where
decidable = recognizable intersect co-recognizable.]

Open question:  P ?= NP intersect coNP  (No strong concensus.)

Open question:  NP ?= coNP  (Strongly believed to be NO.)

Open question:  P ?= NP  (Strongly believed to be NO.)

Answering these questions is worth 1 million dollars!  (They are some of
the "Millenium Problems" recognized by the Clay Mathematics Institute.)

---------------------
Polytime reducibility
---------------------

Defn:  Language A is "polytime reducible" to language B (written A <=p B)
if there is a polytime computable function f : Sigma* -> Sigma* such that
for all w in Sigma*, w in A iff f(w) in B.

Almost identical to many-one reducibility, with added constraint that f can
be computed in polytime.

Just like <=m, think of "<=p" as comparing the difficulty of deciding the
languages.  So A <=p B intuitively says "A is no more difficult to solve
than B" or equivalently, "B is at least as hard to solve as A".

Theorem:  A <=p B and B in P (or NP) -> A in P (or NP).
Main proof idea:  On input x (or <x,c>), compute f(x), in polytime, then
    run decider for B on f(x) (or verifier for B on <f(x),c>), in polytime.

Corollary: A <=p B and A not in P (or NP) -> B not in P (or NP).

Example of polytime reduction: 3SAT <=p CNFSAT