Problems

An instance of the problem: specifying particular params.

Example: Traveling Saleman Problem

Params:

• $C = \{c_1, \dots, c_n\} \rightarrow$ cities.
• $d(c_i, c_j)$.

Solution:

• an ordering $<c_{\pi(1)}, c_{\pi(2)}, \dots, c_{\pi(m)}>$ of cities that minimizes $$ [\sum_{i = 1}^{m - 1} d(c_{\pi(i)}, c_{\pi(i + 1)})] + d(c_{\pi(m)}, c_{\pi(1)}) $$

One instance:

• $C = {c_1, c_2, c_3, c_4}$.
• $d(c_1, c_2) = 10$, $\dots$

$\rightarrow$ a solution $<c_1, c_2, c_4, c_3>$.

Algorithms

Think of them as being computer programs.

Intractable

A problem has not been “well-solved” until a polynomial time algorithm is known for it.

Encoding Scheme

Algorithm operates on encoded inputs, not abstract objects $\rightarrow$ choice of encoding scheme affects SIZE of inputs (n).

Example

Graph $G = (V, E)$,

vertices $V = \{V_1, V_2, V_3, V_4\}$,

edges $E = \{(V_1, V_2), (V_2, V_3)\}$.

Provably Intractable Problems

two different causes of intractability:

1. Problems that require an exponential amount of time to solve
   • typical definition of an intractable problem.
2. Problems where the solution itself is too large to describe concisely
   • might not be hard to compute, but their output is so vast that it cannot be expressed with a polynomial-length formula.
   • Example: A variant of the Traveling Salesman Problem (TSP) where we want to find all tours with a total length $B$ or less.
     • There could be an exponentially large number of valid tours shorter than B.
     • No polynomial-time algorithm can list all of them.
       explain

       Since the saleman must visit every city exactly once, the number of possible routes: $(n - 1)!$
       Say, even if half of them satisfy the B constraint, time complexity to explicitly list (n - 1)! routes is still $$ \mathcal{O}(\frac{(n - 1)!}{2}) = \mathcal{O}(n!) $$ Using Stirling's Approximation $$ n! \sim \sqrt{2\pi n}(\frac{n}{e})^n. $$ This grows faster than exponential time algorithm. Even if a polynomial-time algorithm exists to check whether a route is valid, writing down all valid routes would take an exponential amount of space.

The 2nd type can be regarded as a sign that the problem is not defined realistically, bc we are asking for more information than we could ever hope to use.

Thus, the focus is primarily on the first type: problems that requires exponential time to solve.

Undecidable Problems

Turing proved that

• The halting problem
• Finitely Presented Groups’ Triviality Problem (Rabin, 1958).
• Hilbert’s Tenth Problem (Matijasevic, 1970).
• Tiling the Plane Problem (Berger, 1966).

Intractable but Decidable Problems

Meyer & Stockmeyer (1972) and Fischer & Rabin (1974).