Unit 13: Intractable Problems

I. Orientation — Efficient Computation and Its Limits

Intractability concerns problems for which no efficient algorithm is known, especially when required resources grow exponentially or faster with input size. Complexity theory studies these limits using mathematical models of computation and asymptotic resource bounds.

A. Defining Framework

The central framework classifies computational problems according to the time or space needed to solve increasingly large instances.

• Problem instance: A particular input to a general problem; for example, a graph (G=(V,E)) is an instance of the Hamiltonian Cycle problem.
• Input size: The number (n) of symbols or bits needed to encode an instance, rather than the numeric magnitude of its values.
  • An integer (x) requires approximately (\log_2 x) bits.
  • An algorithm taking (O(x)) time may therefore be exponential in the encoded input length.
• Decision problem: A problem whose output is either “yes” or “no,” such as whether a graph contains a clique of size at least (k).
• Optimization problem: A problem seeking the best feasible solution, such as the minimum-cost travelling-salesperson tour.
  • Complexity classifications are normally defined for decision problems.
  • An optimization problem often has a related decision form: “Is there a tour of cost at most (B)?”
• Tractable problem: Conventionally, a problem solvable in polynomial time (O(n^c)), where (c) is a constant.
• Intractable problem: A problem for which every known exact algorithm requires superpolynomial time in the worst case.
• Polynomial growth: Bounds such as (O(n)), (O(n^2)), and (O(n^{10})) remain polynomial even when the exponent makes an algorithm impractical.
• Exponential growth: Bounds such as (O(2^n)) and (O(n!)) quickly become prohibitive; (2^{100}) already exceeds (10^{30}).
• Complexity status: “Intractable” does not automatically mean “NP-complete.” Undecidable problems, NP-hard optimization problems, and decidable problems outside NP require separate classifications.

II. Basic Concepts — Languages, Complexity Classes, and Reductions

A. Basic concepts

The basic concepts of intractability formalize problems as languages and compare them through asymptotic complexity and transformations.

• Language model: A decision problem is represented by a language (L\subseteq\Sigma^*), containing exactly the encoded instances whose answer is “yes.”
  • (\Sigma) is a finite alphabet.
  • (\Sigma^*) is the set of all finite strings over (\Sigma).
• Class (P): (P) contains decision problems solvable by a deterministic algorithm in polynomial time:
  
  TEXT

    P = ⋃ₖ TIME(nᵏ)

  
  Here, (n) is input length, (k) is a fixed nonnegative constant, and (\operatorname{TIME}(n^k)) denotes problems decidable within (O(n^k)) deterministic steps.
• Deterministic computation: At each state and input symbol, the machine has exactly one permitted next action; an ordinary sequential program follows this model.
• Class (NP): (NP) contains decision problems whose “yes” instances possess polynomial-size certificates verifiable in deterministic polynomial time.
• Certificate definition: A language (L) belongs to (NP) if a polynomial-time verifier (V) and polynomial (p) exist such that:
  
  TEXT

    x ∈ L  ⇔  there exists y, |y| ≤ p(|x|), with V(x, y) = 1

  
  Here, (x) is an encoded instance, (y) is its certificate, (|x|) and (|y|) are encoding lengths, and (V(x,y)=1) means acceptance.
• Containment relation: (P\subseteq NP), because a polynomial-time solver can verify an instance without needing a meaningful certificate.
• Open question: Whether (P=NP) remains unresolved. If (P=NP), every efficiently verifiable decision problem would also be efficiently solvable.
• Polynomial-time reduction: For languages (A) and (B), (A\leq_p B) means that a polynomial-time computable function (f) satisfies:
  
  TEXT

    x ∈ A  ⇔  f(x) ∈ B

  
  Thus, a solver for (B) can solve (A) after transforming (x) into (f(x)).
• Reduction direction: To show that (B) is at least as hard as (A), reduce (A) to (B), not (B) to (A).
• Transitivity: If (A\leq_p B) and (B\leq_p C), then (A\leq_p C), because the two polynomial transformations can be composed.

B. Applications and Limitations

These classifications guide algorithm design, but they describe asymptotic worst-case behavior rather than guaranteeing practical performance.

1. Theoretical tractability:

   • Polynomial criterion: An (O(n^{100})) algorithm belongs to (P), although it is unlikely to be usable.
   • Robustness: Standard deterministic computational models simulate one another with at most polynomial overhead, making (P) relatively model-independent.

2. Practical solvability:

   • Small instances: An (O(2^n)) algorithm can be useful when (n) is small or preprocessing greatly reduces it.
   • Special structure: Restricted cases may be polynomial; for example, 2-SAT is solvable in linear time even though general SAT is NP-complete.
   • Alternative methods: Approximation algorithms, heuristics, randomized algorithms, parameterized algorithms, and branch-and-bound may handle instances without resolving their worst-case hardness.

• Worst versus average case: NP-completeness concerns worst-case instances; it does not prove that every instance is difficult.
• Lower-bound caution: Calling a problem NP-complete does not prove that it requires exponential time unless an additional assumption such as (P\ne NP) is adopted.

III. Non-deterministic Algorithms — Guessing and Polynomial Verification

A. Non-deterministic algorithms

A non-deterministic algorithm conceptually explores multiple permitted choices simultaneously and accepts if at least one computation path reaches an accepting state.

• Non-deterministic choice: A step may select any value from a finite set without deterministically searching through all values.
• Acceptance rule: A “yes” instance is accepted when at least one branch succeeds; a “no” instance is rejected only when every branch fails.
• Conceptual model: Non-determinism is a mathematical abstraction, not an assertion that conventional hardware can examine exponentially many branches for free.
• Polynomial-time condition: An NP algorithm must have at least one accepting path of polynomial length for every “yes” instance, while all branches halt within a polynomial number of steps.
• Guess-and-check form: A non-deterministic algorithm guesses a certificate and verifies it deterministically:
  
  TEXT

    NONDETERMINISTIC-CLIQUE(G, k)
        guess a set S of k vertices
        for every distinct u, v in S
            if {u, v} is not an edge of G
                reject this branch
        accept this branch

  
  (G=(V,E)) is an undirected graph, (k) is the requested clique size, (S\subseteq V), and ({u,v}\in E) indicates adjacency.
• Verification cost: The guessed set uses polynomial space, and checking all vertex pairs takes (O(k^2)) adjacency tests.
• Equivalence: Polynomial-time non-deterministic computation and polynomial-time deterministic certificate verification define the same class, (NP).
• Deterministic simulation: A deterministic machine can enumerate all possible certificates, but if a certificate has (p(n)) bits, as many as (2^{p(n)}) candidates may exist.

B. Significance and Limitations

Non-determinism separates the difficulty of discovering a solution from the difficulty of checking a proposed solution.

• Search versus verification: Finding a Hamiltonian cycle may be difficult, but checking a listed cycle requires confirming that each vertex occurs once and that consecutive vertices are adjacent.
• One-sided evidence: Certificates naturally establish “yes” answers; a failed guessed certificate does not establish that no valid certificate exists.
• Class (coNP): (coNP) contains languages whose complements are in (NP); equivalently, their “no” instances have polynomially verifiable certificates.
• Unknown equality: It is not known whether (NP=coNP). A proof that a propositional formula is unsatisfiable is not known to have a polynomial-size certificate in all cases.
• Implementation reality: Coding guess as random selection does not create a correct NP decision procedure, because random failure cannot prove that no successful branch exists.
• Analytical value: The model provides a concise way to establish membership in (NP): specify a polynomial-size certificate and a polynomial-time verifier.

IV. NP-Completeness — The Hardest Problems in NP

A. NP-completeness

NP-completeness identifies decision problems that belong to (NP) and are at least as hard as every other problem in (NP).

• NP-hardness: A problem (H) is NP-hard if every language (L\in NP) satisfies (L\leq_p H).
• NP-completeness: A decision problem (C) is NP-complete exactly when:
  1. (C\in NP).
  2. (C) is NP-hard.
• Consequences: If one NP-complete problem has a deterministic polynomial-time algorithm, then every problem in (NP) does, implying (P=NP).
• Cook–Levin theorem: Boolean Satisfiability, SAT, is NP-complete. SAT asks whether some truth assignment makes a Boolean formula true.
• Typical examples: 3-SAT, CLIQUE, VERTEX-COVER, HAMILTONIAN-CYCLE, SUBSET-SUM, and the decision version of Travelling Salesperson are NP-complete.
• Proof pattern: To prove a new problem (B) NP-complete:
  1. Show (B\in NP) by giving a certificate and polynomial-time verifier.
  2. Select a known NP-complete problem (A).
  3. Construct a polynomial-time reduction (A\leq_p B).
  4. Prove both directions: (x\in A) if and only if (f(x)\in B).
• Concrete reduction relation: CLIQUE and VERTEX-COVER are connected through graph complementation within the same graph:
  
  TEXT

    G has a clique of size k
    ⇔ G has an independent set of size k
    ⇔ G has a vertex cover of size |V| − k

  
  In the first equivalence, the clique is considered as an independent set in the complement graph; in the second, the complement of an independent set is a vertex cover.

B. Applications and Limitations

NP-completeness results redirect effort from searching indefinitely for exact polynomial algorithms toward methods suited to the application.

• Algorithm selection: Exact exponential algorithms remain appropriate for small instances, while approximation or parameterized methods may scale better.
• Approximation distinction: NP-completeness of an exact decision problem does not determine how closely its optimization version can be approximated.
• Restricted inputs: Hardness of a general problem does not transfer automatically to every restricted version; graph structure such as bounded treewidth can permit efficient algorithms.
• NP-hard beyond NP: An optimization problem or even an undecidable problem may be NP-hard without being NP-complete, because NP-completeness requires membership in (NP).
• Proof limitation: A reduction demonstrates relative difficulty, not an unconditional exponential lower bound.
• Central implication: Under the widely used assumption (P\ne NP), no NP-complete problem has an exact deterministic polynomial-time algorithm for all inputs.