• Problem, parameter, problem instance, solution

• Algorithm, polynomial-time algorithm

• Input length

• Worst-case time/space complexity

• Complexity class P

• Decision problem, optimization problem

• Polynomial time verification algorithm

• Complexity class NP and CO-NP

• Reduction problem between problems

II. New for today:

• Complexity of reduction

• Complexity relationship due to reduction R

If p ₁® p ₂, then T(p ₁) £ T(p ₂) + T_R where T(p ) is the time complexity of p ; T_R is

the time complexity of reduction. Using polynomial reduction time

p ₂ provides a low-bound of the complexity of p ₁.

R: i₁ ® i₂

T₁(|i₁|) £ T_R(|i₁|) + T₂(|i₂|)

If the reduction is polynomial time, then p ₂ is at least as hard as p ₁.

• NP-complete and NP-hard problem

How to prove a problem is

        -NP-hard

        -NP-complete

Every problem in NP can be reduced in polynomial-time to the CIRCUIT-satisfiability problem.

Conclusion: CIRCUIT-satisfiability is the "hardest" problem in NP.

• C-SAT is in NP

• A problem p is NP-complete if
(1)  Every problem in NP can be reduced in polynomial time to it;
(2)  p is in NP.
• A problem p is NP-HARD if:

Every problem in NP can be polynomial-time reduced to it.
So every NP-complete problem must be NP-HARD.

• All NP-complete problem can be reduced to each other in polynomial time.

Examples:

SAT (SATisfiability) problem:

    The first expression is not in 3CNF, because both the first and the second clauses contain more than 3 literals (4 literals
    in this example), but it can be logically converted to 3CNF as follows:

    (X₁Ú X₂Ú Ø Y₁) Ù (Y₁Ú Ø X₄Ú X₆) Ù (X₃Ú Ø X₂Ú Ø Y₂) Ù (Y₂Ú X₄Ú X₅) Ù (X₁Ú Ø X₂) Ù (X₄Ú X₅)

    The logical equivalence between this expression and the original one can be proved using a truth table to see whether both
    expressions return the same value.

    In general, if a boolean expression has one or more term(s) with more than 3 literals, the expression is not in 3CNF.
    However, this expression can be logically converted into one in 3CNF by the addition of new vaiables (such as y₁, y₂, in
    the example above).

Clique Problem:

    Instance of the problem: an undirected graph G, and an integer K.

    Question: Does the graph have a "clique" of size at least K?

    A clique in an undirected graph G = (V, E) is a subset V’ Í V of vertices, each pair of which is connected by an edge in E.
    In other words, a clique is a complete subgraph of G. The size of the clique is the number of vertices it contains.

    To prove that CLIQUE is NP-complete, we need show:

•     CLIQUE is in NP;
•     CLIQUE is NP-hard

    2. We next show that the clique problem is NP-hard by proving that 3-SAT £ p CLIQUE. The reduction algorithm begins
    with an instance of 3-SAT. Let F=C₁Ù C₂Ù _{× × ×} Ù C_m be a boolean formula in 3-CNF with m clauses and n variables. For
    r = 1, 2, …, m, each clause C_r has exactly three distinct literals l₁^r, l₂^r, and l₃^r. We shall construct a graph G such that F is
   satisfiable if and only if G has a clique of size m.  The graph G= (V, E) is constructed as follows. For each clause
    C_r = (l₁^rÚ l₂^rÚ l₃^r) in F, we place a triple of vertices v₁^r, v₂^r, and v₃^r in V. We put an edge between two vertices v_i^r and v_j^s
    if both of the following hold:

• v_i^r and v_j^s are in different triples, that is, r ¹ s, and
• Their corresponding literals are consistent, that is, l_i^r is not the negation of l_j^s.

    F = (X₁Ú X₂Ú ØX₇) Ù (X₇Ú ØX₄Ú X₆) Ù (X₃Ú ØX₂Ú ØX₈) Ù (X₈Ú X₄Ú X₅) Ù (X₁Ú ØX₂) Ù (X₄Ú X₅),

    Then the graph in Figure 2. shows all the edges in the G incident on one of the vertices corresponding to the first literal
    in the first clause.
 

    Figure 2 The graph derived from the 3-CNF formula F = C₁Ù C₂Ù C₃Ù C₄Ù C₅Ù C₆, where C₁= (X₁Ú X₂Ú ØX₇),
    C₂=   (X₇Ú ØX₄Ú X₆), C₃= (X₃Ú ØX₂Ú ØX₈), C₄= (X₈Ú X₄Ú X₅), C₅= (X₁Ú ØX₂), and C₆= (X₄Ú X₅), in reducing
    3-CNF-SAT to CLIQUE. A satisfying assignment of the formula is (X₁ = 1, X₂ = 0, X₃ = 0, X₄ = 0, X₅ = 0, X₆ = 1,
    X₇ = 1, X₈ = 1), corresponding to the clique with green shaded vertices. In this example, X₁ is connected to every vertex
    except ØX₁.

    Now we have shown how to construct an instance of a clique.

    Claim: F is satisfiable if and only if G has a clique of at least size k.

    Proof (in both ways)

    (Þ ) First, suppose that F has a satisfying assignment. Then, each clause C_r contains at least one literal l_i^r that is assigned 1,
    and each such literal corresponds to a vertex v_i^r. Picking one such "true" literal from each clause yields a set of V’ of k
    vertices. We claim that V’ is a clique. For any two vertices v_i^r, v_j^r Î V’, where r ¹ s, both corresponding literals l_i^r and l_j^s
      are mapped to 1 by the given satisfying assignment, and thus the literals cannot be complements. Thus, by the construction
    of G, the edge (v_i^r, v_j^s) belongs to E.

    (Ü ) Conversely, suppose that G has a clique V’ of size k. No edges in G connect vertices in the same triple, and so V’
    contains exactly one vertex per triple. We can assign 1 to each literal l_i^r such that v_i^r Î V’ without fear of assigning 1 to both
    a literal and its complement, since G contains no edges between inconsistent literals. Each clause is satisfied, and so F is
    satisfied. (Any variables that correspond to no vertex in the clique may be set arbitrarily.)