Computational Intractability

Size of input:

• Total number of (binary bits) for encoding the input, for int $a<1$ is $[{\log }_2(a)]$
• ex, Encoding:
  • weighted directed graph problem: $T={\sum }_{i,j=1}^n[{\log }_2(a_{ij})]$
  • Subset Sum Problem: $T={\sum }_{i=1}^n[{\log }_2{a}_i]+[{\log }_{2}S]$
  • Knapsack Problem: $T={\sum }_{i=1}^n[{\log }_2{p}_i]+[{\log }_2{w}_i]+[{\log }_{2}C]$
  • weighted Interval Scheduling Problem: $T={\sum }_{i=1}^n[{\log }_2{s}_i]+[{\log }_2{f}_i]+[{\log }_2{v}_i]$

Computational tracability:

• A problem is computational tractable if it admits a polynomial-time algorithm
  • otherwise intraceable
• Traceable problems:
  • Shortest path problem: $O(n,m)$
  • Weighted Interval Scheduling Problem: $O(n\log n)$
  • Max flow $O(n{m}^2)$
  • 2 coloring: $O(m)$
  • Stable matching $O(n^2)$
• Probably intractable:
  • Hamiltonian path: $O(n^2.2^n)$
  • Subset sum $O(nS)$
  • Knapsack: $O(nP)$

Polynomial-time reduction:

• $X{\le }_{P}Y$: Problem X polynomial reduces to problem Y if arbitrary instances of problem X can be solved using:
  • Polynomial number of computational steps
  • then polynomial number of calls to oracle that solves problem Y
• We pay for time to write down instances sent to black box → instances of Y must be of polynomial size
• If we have problem $G$, we can turn it to another problem $G^{\prime }$ with polynomial time
  • example: graph $G$ is maximum matching problem, add a source node and link to all nodes from A and all nodes from be link to a sink, therefore reduce to polynomial complexity of $G^{\prime }$
• Purpose. Classify problems according to relative difficulty.
• Designing algorithms. If $X{\le }_{P}Y$ and Y can be solved in polynomial-time, then $X$ can also be solved in polynomial time.
• Proving intractability. If $X{\le }_{P}Y$ and X cannot be solved in polynomial-time, then Y cannot be solved in polynomial time.
• Establishing equivalence. If $X{\le }_{P}Y$ and $Y{\le }_{P}X$, then $X{\equiv }_{P}Y$

Reduction strategies:

• Reduction by simple equivalence
  • Independent Set
  • Vertex Cover: Given a graph $G=(V,E)$ and an integer $k$,
    • is there a subset of vertices $S\subseteq V$ such that $|S|\le k$, and for each edge, at least one of its endpoints is in $S$?
  • Claim: Vertex coverd ${\equiv }_P$ Independent set

    • proof: we show $S$ is an independent set iff $V\backslash S$

        - Let S be any independent set, consider an arbitrary edge $(u,v)$
        - S is independent $\to u\not \in S$ or $v\not \in S\to u \in V\backslash S$ or $v\in V\backslash S$
        - Thus $V\backslash S$ covers edge $(u,v)$
      

      - - Let $V\backslash S$ be any vertex cover, consider 2 nodes $u\in S$ and $v\in S$ - Observe that $(u,v)\notin E$ since $V\backslash S$ is a vertex cover - Thus, 2 nodes in $S$ are joined by an edge $\to S$ is an independent set
• Reduction from special case to general case
  • Set cover: Given a set $U$ of elements, a collection $S_1,S_2,...,S_m$ of subsets of U, and an integer $k$, does there exist a collection of $\le k$ of these sets whose union is equal to $U$?
  • Claim: Vertex-cover ${\le }_P$ Set-cover
    • Proof: Given a VERTEX-COVER instance $G=(V,E),k$, we construct a set cover instance whose size equals the size of the vertex cover instance
    • Construction: Create SET-COVER instance: $k=k,U=E,S_v=\{e\in E:e\text{ incident to }v\}$
    • Set-cover of size $\le k$ iff vertex cover of size $\le k$
• Reduction by encoding with gadgets
  • Boolean Stisfiability Problem:
    • Literal: a boolean var, $x$ and $\bar{x}$
    • Clause: A disjunction of literals: $A=x\vee y\wedge z...$
    • Conjuntive Normal Form, CNF: A propositional fornula $\Phi$ that is the conjunction of clauses
    • Given CNF formula $\Phi$, does it have a satisfying truth assignment? if yes $\Phi$ is satisfiable
      • 2-SAT, 3-SAT, n-SAT: Boolean Satisfaction problem where each clause contains exactly 2 literals
  • Claim: 3-SAT${\le }_P$ Indepdent-set
    • Given an instance $\Phi$ of 3-SAT, we construct an instance $(G,k)$ of INDEPENDENT-SET that has an independent set of size k iff $\Phi$ is satisfiable
    • Construction.
      • G contains 3 vertices for each clause, one for each literal.
      • Connect 3 literals in a clause in a triangle.
      • Connect literal to each of its negations
    • Claim: $G$ contains independent set of size $k=|\Phi |$ iff $\Phi$ is satisfiable
• Transitivity: If $X{\le }_{P}Y$ and $Y{\le }_{P}Z$ then $X{\le }_{P}Z$

Types of problems:

• A problem can be 1 or combination of these types
  • Decision Problem
    • P-class, polynomial includes:
      • Map Coloring
      • Max Flow
      • Shortest Path
      • Checking if a number is prime
    • Not known to be in P:
      • HAMILTONIAN CYCLE
      • SUBSET SUM
      • PARTITION
      • KNAPSACK
      • INDEPENDENT SET
      • SET COVER
      • VERTEX COVER
      • SAT
      • 3-SAT
      • and many others
  • Search Problem
  • Optimizatino Problem

Solving and checking:

• Solving a problem might not be polynomial but checking a possible solution is poly-time
• Efficient certification:
  • A “checking” algorithm for a decision problem X has a different structure from an algorithm that solves X
  • Certificate: a (possible) solution t
  • Certifier: a checking algorithm
• An algorithm B is an efficient certifier for a problem X if, for every instance s of X, and for every candidate t
  • B has polynomial running time (in the size of s and t), and
  • B can verify whether t is a solution to s
• ex:
  • Independent Set
    • Certificate: t is a set of at least k vertices
    • Certifier: verifies that no pair of these vertices are connected to an edge
  • Is a given nb composite
    • certificate is a non-trivial factor t of n
    • certifier is a function to check if t is divisible by n
  • Hamilton Cycle
    • Certificate. A permutation of the n nodes
    • Certifier. Check that the permutation contains each node in V exactly once, and that there is an edge between each pair of adjacent nodes in the permutation
  • Boolean Stisfiability Problem:
    • Certificate. An assignment of truth values to the n boolean variables.
    • Certifier. Check that each clause in s has at least one true literal