19_Algorithm Engineering: Problem Complexity II

Proving a Problem is in NP

• To prove problem X is in NP, follow these steps:
  1. Define the data type for a candidate solution.
  2. Prove each candidate fits in polynomial space.
  3. Design a verification algorithm for Problem X.
  4. Prove the verification is polynomial.
  5. Conclude that X belongs to NP ( $X \epsilon NP$).

P vs NP

• $X \epsilon P$ implies $X \epsilon NP$.
  • NP is the set of problems verifiable in polynomial time.
  • P is the set of problems solvable in polynomial time.
  • If a problem can be solved in polynomial time, it can be verified in polynomial time.
• Proof:
  • By definition of P, there exists an algorithm solve_X that returns a correct solution to X in polynomial time.
  • A verifier algorithm can be created by reduction to solve_X.
  • Therefore, $P \subseteq NP$
• Further Proof:
  • solve_X can be used to generate a correct solution and determine if that solution is better than a candidate solution.
  • Assuming the "solution IS BETTER THAN candidate" part takes polynomial time, both versions of verify_X are correct and polynomial.
  • Hence there exists a polynomial verification algorithm for X, and by the definition of NP, $X \epsilon NP$

Decidable vs Undecidable Problems

• Problem X is decidable if there exists an algorithm that solves X; otherwise, it is undecidable.
  • Every problem in P is decidable.
    • A decision problem has a Boolean output (yes/no).
    • When a decision problem is solvable, it is “decidable”; otherwise, it is “undecidable.”
  • Proving that a problem is decidable is simpler than proving it is in P.
    • We only need to show that there exists a correct algorithm; efficiency analysis is not required.
  • The circuit satisfaction and traveling salesperson problems are decidable.
  • Every problem in NP is decidable.
• Examples of undecidable problems:
  • Ill-posed problems: the output definition precludes any algorithm from being provably correct.
    • Example: the meaning of life problem:
      • Input: a string K containing the sum of human knowledge.
      • Output: a string M containing an English sentence describing the meaning of life.
      • There is no way to design a correct algorithm because the definition of a correct output is subjective.
  • Problem X, such that any algorithm (Solve_X) attempting to solve Problem X does not terminate.

Undecidable Problems Continued

• A problem may be undecidable when any process with the potential to solve the problem may fail to terminate.
• Example: PCP (Post Correspondence Problem) and the Halting Problem
  • PCP (Emil Post, 1946):
    • Input: Two finite lists: $\alpha<em>1, \alpha</em>2, …, \alpha<em>N$ and $B</em>1, B<em>2, …, B</em>N$ of words over some alphabet A with at least two symbols.
    • A solution is a sequence of indices $(i<em>k)</em>{1 \leq k \leq K}$ with $K \geq 1$ and $1 \leq i_i \leq N$ for all k, such that the output is True if such a solution exists, and False otherwise.
    • PCP may not terminate because there is an endless supply of α-blocks and β-blocks to keep the algorithm running in search of a solution.

Venn Diagram Representation

• Illustrates relationships between decidable, P, NP, and undecidable problems.
• Examples shown:
  • Decidable: Sorting.
  • P: SSSP (Single Source Shortest Path), MST (Minimum Spanning Tree).
  • Undecidable: Halting problem, PCP.

NP-Completeness

• NP-completeness is the third major category of problem complexity.
• Reminder: NP is the set of problems for which verifier algorithms have polynomial time and space complexity.

Proving NP-Completeness

• (No specific steps provided in this section of the transcript)

NP-Hardness

• NP-Hardness describes the hierarchical hardness of a problem relative to other problems in the NP Class.
• Other definitions:
  • A class of problems that are informally “at least as hard as the hardest problems in NP.”
  • The complexity class of decision problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time.
  • A problem is NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem (nondeterministic polynomial time) problem.

Reducibility of NP-Hard Problems

• Problem E reduces to problem H if there exists an algorithm that solves E by pre-processing its input, solving H, then post-processing that output.
  • Diagram illustrates the process:
    • Input E is pre-processed to create Input H.
    • Input H is solved to produce Output H.
    • Output H is post-processed to create Output E.

Reducibility of NP-Hard Problems (Continued)

• Given: $E \longrightarrow H$
  • If H can be solved in polynomial time, then E can be solved in polynomial time.
  • If E cannot be solved in polynomial time, then H cannot be solved in polynomial time.

Reducibility of NP-Hard/NP-Complete Problems

• Problem H is NP-Hard if, for any problem $E \epsilon NP$, $E \longrightarrow H$
  • Any problem in NP can be solved by reducing it in polynomial time to H.
• Problem H is NP-Complete if:
  • $H \epsilon NP$
  • H is NP-Hard
• Recall:
  • NP Class includes all problems that cannot be solved in polynomial time (P).
  • For problems in NP, given a (instance, certificate) pair, checking whether the certificate is a correct output for that instance of problem H can be done in polynomial time.

NP-Hard vs NP-Complete

Boolean Circuit Evaluation

• (Section contains no specific details in the transcript)

Circuit Satisfaction Problem

• Definition:
  • Input: A Boolean circuit C with k variables and n vertices.
  • Output: A Boolean assignment A that satisfies C, or None if no such assignment exists.
• The Circuit Satisfaction Problem is NP-Complete (Cook-Levin Theorem).
  • To prove this, one needs to show that:
    • CSP is in NP ($CSP \epsilon NP$)
    • CSP is NP-Hard

Circuit SAT Example

• Diagram of a Boolean circuit with AND, OR, and NOT gates, and input variables $x<em>1$ through $x</em>5$.
• The goal is to find a satisfying assignment.

Proof of Cook Levin’s Theorem

• Reduce an arbitrary problem E in NP to H.
• Let A be a non-deterministic polynomial time algorithm for E.
• Convert A to a circuit, so that E is a Yes instance if and only if the circuit is satisfiable.

Circuit Satisfaction ∈ NP

• A candidate solution is an assignment of a Boolean value to each of the K variables in the circuit.
• A circuit with n vertices has at most n variables, so $k \leq n$ and $O(k) \subseteq O(n)$
• An assignment may be verified by evaluating the input circuit and testing whether the output is True.
  • Each candidate may be verified in O(n) time (polynomial).

Circuit Satisfaction is NP-Hard

• For any problem $E \epsilon NP$, $E \longrightarrow H$ (assuming H is CSP).
• Since $E \epsilon NP$ there must be some verifier algorithm, verify_E, that takes a (instance, certificate) pair as input and outputs Yes or No if the certificate is a correct output for the instance.
• Develop a Boolean circuit that emulates the execution of verify_E.
• The circuit output shall be equivalent to that computed by verify_E.

Circuit-satisfiability problem is NP-hard (Continued)

• Since E is in NP, there is a poly-time algorithm A which verifies E.
• Suppose the input length is n. Let T(n) denote the worst-case running time.
• Let k be the constant such that $T(n) = O(n^k)$ and the length of the certificate is $O(n^k)$.

CIRCUIT-SAT is NP-complete

• In summary:
  • CIRCUIT-SAT belongs to NP, verifiable in poly time.
  • CIRCUIT-SAT is NP-hard; every NP problem can be reduced to CIRCUIT-SAT in polynomial time.
  • Thus, CIRCUIT-SAT is NP-complete.

Problem Complexity in Brief

Problem Complexity: Examples

P, NP, NP-Hard and NP-Complete (Diagram)

• Illustrative diagram showing the relationships between complexity classes.

P Versus NP Problem

• Any NP-complete problem H is NP-hard, so $E \longrightarrow H$ for any $E \epsilon NP$.
• H is also in NP.
• Therefore, any NP-complete problem may serve as E or H in the expression $E \longrightarrow H$.
• Consequently, every NP-complete problem is polynomial-time reducible to every other NP-complete problem.
  • For any complete problems X and Y: $X \longrightarrow Y$ and $Y \longrightarrow X$
• Therefore, if any NP-complete problem may be solved in polynomial time, then all NP-complete problems may be solved in polynomial time.

Is P=NP or P ⊂ NP?

• There are currently no proofs that $P = NP$ or $P \neq NP$.
• A 2012 poll of 100 complexity theory researchers obtained:
  • 78% of those who registered an opinion feel that $P \subset NP$
  • There is significant doubt around this issue on the part of experts.
  • There is no scientific consensus!