Chapter 34 Answers

Document last modified:

Introduction

Question 1 How can you prove the difference between a program in an infinite loop or just taking a long time? Cannot.

Question 2

What is the class of the following algorithm? Θ(n³)

Is the trivial lower bound of Ω(n²) useful in this case? Yes, it is the lower-bound based on inputs.

MatrixMultiplication( A[n,n], B[n,n], C[n,n])

for i ←1 to n do

for j ← 1 to n do

C[i,j] ←0

for k ← 1 to n do

C[i,j] ← C[i,j]+A[i,k]*B[k,j]

Question 3

What questions would the questioner ask to ensure that the answer was always found after ⌈lg n⌉ questions? Similar to binary search.

How many questions are needed to determine the number for n=8? 3

Give the decision tree for n=8.

            1-8
<5       /    \
       1-4    5-8
<3   / \ <7 / \
1-2 3-4 5-6 7-8
/ \    /\    /\   /\
1   2 3 4 5 6 7 8

Example: Nondeterministic graph coloring

Use 4 colors to color 5 vertices with all adjacent vertices a different color.

Question 4

What is the complexity of verifying the answer? Θ(n)

Do you think it is generally of lower complexity to verify an answer than find a solution? Yes.

What is the complexity of verifying a list is sorted? Θ(n)

Reductions

Question 5

What is the complexity of B? Polynomial.

What is the complexity of A? We don't specify. If we can reduce A → B then A is polynomial.

What is α? What is A(α)? The input to A. An instance of A.

What is β? What is B(β)? The input to B after reducing α. An instance of B.

What is the work of the reduction algorithm in this case? Reducing α to b.

The First NP-Complete Problem

Question 6 To develop some intuition on determinism and NP-completeness, do the following on Figure (b) below:

How would you solve for one output solution for x₁, x₂ and x₃?
for x₁= 0 to 1
    for x₂= 0 to 1
        for x₃= 0 to 1
           if ((^¬x₃∧ x₁∧ x₂)∨^¬x₃)∧ ((x₁∨x₂)∨^¬x₃)∧ (^¬x₃∧ x₁∧ x₂) return ( x₁, x₂, x₃)

Try to guess and verify one solution for x₁, x₂ and x₃. Your guess is nondeterministic but the verification is deterministic.

Guess x₁, x₂ and x₃(all true) yields true by plugging in boolean values into expression.

What is the worst-case complexity in determining the input to produce an output of 1? O(2ⁿ) for n variables.

What is the complexity in verifying a given input produces an output of 1? Consider the number of operations (gates) that must be evaluated. Θ(n) for n operations (gates), can assume same time for And, Or and Not operation regardless of input number.

Polynomial Time 34.1

Abstract Problems

Question: Give another (i_j, s_k) ∈ SPAP. i_j=(G, y, x), s_k=<y, z, x>

Formal Language Framework

Question: What is {0, 1}^*? You can think of this in terms of EBNF from programming languages. {ε, 0, 1, 00, 01, 10, 11, 000, ... }

L_odd = {1, 11, 101, 111, 1001, ...}

∑^* = {ε, 0, 1, 00, 01, 10, 11, 000, ... }

Question: What is L_odd? {ε, 0, 00, 10, 000, ... }

Question: What is L₁² for L₁ = {0, 1}?{00, 01, 10, 11}

Decision problem Q

Question:

Is <G, s, x, 1> one instance of PATH_L? Yes

Is <G, s, z, 1> one instance of PATH_L? No.

Relation Between Decision Problems and Algorithms

A_PATH works as follows on graph G:

verifies that G correctly encodes an undirected graph. Question a and b - is correctly encoded.

verifies that u and v are vertices in G. Question a and b - s and x are vertices of G.

uses breadth first search to compute the shortest path from u to v in G. Question a and b - shortest path between s and x is <s,y,z,x>.

compares the number of edges found in the shortest path to k. Question a - 3 < 4.

If G correctly encodes an undirected graph, and if the number of edges in the shortest path from u to v is less than or equal to k, then A_PATH outputs a 1 and halts. Otherwise A_PATH runs forever. Question a - runs forever. Question b - outputs 1 and halts, accepts.

A_PATH works the same as above, but if G correctly encodes an undirected graph, and if the number of edges in the shortest path from u to v is less than or equal to k, then A_PATH outputs a 1 and halts. Otherwise A_PATH outputs a 0 and halts. Question a - outputs 0, rejects. Question b - outputs 1, accepts and .

We don't know if A_PATH decides PATH_L only that decided a and b.

Question a

For the instance of PATH_L:

V= {s,y,z,x}
E = {(s,x),(x,y),(y,x),(y,z),(s,y)}
G = (V, E)

Would A_PATH<G, s, x, 2>

accept?

reject?

decide?

Question b

What about A_PATH<G, s, x, 4>

34.2 Polynomial time verification

Algorithm's that verify membership in a language

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. Remember Circuit-Satisfiability has exponential (2ⁿ) complexity yet we can easily verify in polynomial time:

((^¬x₃∧ x₁∧ x₂)∨^¬x₃)∧ ((x₁∨x₂)∨^¬x₃)∧ (^¬x₃∧ x₁∧ x₂)

34.3 NP-Completeness and Reducibility

Reducibility - tool for proving languages belong to class P

Example

A₁ decides Hamiltonian cycle visits each vertex exactly once.

L₁language of Hamiltonian cycle instances.

Example: A₁( G )

A₂ decides k-cycle is a cycle of length exactly k unique vertices.

L₂language of exactly k unique vertices cycle length instances.

Example: A₂( G, 5 )

For a graph with v vertices:

we can answer the question: does a Hamiltonian cycle exist?

with the question: does a cycle of length v exist?

The answer to both questions is the same.

Question

What is x? G
What is L₂? L₁, k
What is A₁(x)? 1
What is f(x)? G, 5
What is A₂( f(x) )? 1
What is the work of the reduction algorithm F in this case? Generate f, a function that inputs G and outputs G, 5.
L₁ ≤_pL₂? Yes.
L₂ ≤_pL₁? Yes. f^-1((G,5))=G

V= {1,2,3,4,5}
E = {(1,2),(2,1),(1,5),(5,1),...}
G = (V, E)

Question: What does the lemma imply about L₁ if L₁ ≤_pL₂? L₂ ∈ P implies L₁ ∈ P, if we have a polynomial time algorithm deciding L₂ we have a polynomial time algorithm deciding L₁ also.

NP-completeness

34.4 NP-completeness proofs