Our discussions will continually move back and forth between informal (SL) and formal (TM) representations, used to express the same ideas.
A decision problem π is a general queston (to be answered "yes" or "no"), usually possessing several parameters, whose values are left unspecified. Such a problem is described by giving:
INSTANCE: A general description of all of its parameters;
QUESTION: A precise statement of the question requiring yes/no answer.
A particular instance of the problem is given by specifying particular values for each of the problem parameters. Corresponding to each problem is the notion of the size of a problem instance. When an algorithm is given (SL or TM) and said to solve a decision problem π (with correct "yes" or "no" answers for every instance), one is interested to know the time complexity function, expressing for each size, the largest amount of time required to compute the answer, over all problem instances of that size.
| item | informal | formal |
|---|---|---|
| decision problem | INSTANCE + QUESTION | language |
| algorithm | DSL program P | DTM program M |
| time complexity | TP(n) | TM(n) |
| size | intuitive | length of tape |
A deterministic structured language (DSL) program P over algebras Ai is constructed recursively over assignment statements v → e (for allowable expressions e of the various algebras), using the three structured programming constructs:
and its complexity TP(n) is computed over T(v → e) = 1 + T(e) recursively, asA deterministic Turing machine (DTM) program M over alphabet Σ consists of:
(1) a superalphabet Γ⊇Σ with "blank" b∈Γ∼Σ;
(2) a finite set Q of states with distinguished "start" state q0 and two distinguished "halting" states qY and qN;
(3) a transition function δ: (Q ∼ {qY, qN}) x Γ → Q x Γ x {-1,0,1}
and its complexity TM is given by the expression:
SHORTEST PATH - GRAPHS
INSTANCE: Graph G = (V, E), two vertices u, v and positive integer k.
QUESTION: Is there a path in G from u to v of length ≤ k?
TRAVELING SALESMAN
INSTANCE: Finite set C = {c1, c2, ... , cn} of "cities", positive integer-valued distance function d(ci, cj) for all i, j and positive integer B.
QUESTION: Is there a "tour" visiting each city just once with the sum of the distances ≤ B?
INTEGER DIVISIBILITY BY FOUR
INSTANCE: Positive integer N (encoded in binary).
QUESTION: Is there an integer m with N = 4m?
A function T(n) is of order f(n) and we write T(n) = O(f(n)) if there is a constant c such that |T(n)| ≤ c|f(n)| from some point on.
NOTE: aknk + ak-1nk-1 + ... + a1n + a0 = O(nk)
See G&J, Figures 1.2 and 1.3.
A polynomial-time algorithm (e.g., P or M) is one whose time complexity function (TP(n) or TM(n)) is O(p(n)) for some polynomial p, where n is the size. One whose time complexity function cannot be so bounded is called an (at least) exponential-time algorithm. A tractable problem is one having a polynomial-time deterministic algorithm as its solution (it is in the class P). All other problems are said to be intractable. The intractability of a problem can be shown to be independent of the encoding scheme used to represent its instances and the algorithmic model used for computing its time complexity, so long as "reasonable" choices are made.
Among the provably intractable problems are the algorithmically unsolvable (undecidable) problems (e.g., the "halting problem" for Turing machines), intractable in an especially strong sense. All provably intractable problems known to date are in fact "nondeterministically" intractable, i.e., they cannot be solved in polynomial time using even a nondeterministic computational model.
Most of the apparently intractable problems encountered in practice are decidable and can be solved in polynomial time with a nondeterministic computer model (they are in the class NP). But none of the proof techniques so far developed are able to verify this (apparent) intractability.
Cook's Theorem (1971): The SATISFIABILITY problem has the property that every problem in NP can be polynomially reduced to it.
Such problems are said to be NP-complete, and they are then, in a sense, the "hardest" problems in NP. If one of them is in P, then they are all in P (and in fact, all of NP would be in P, so that NP = P -- thought to be extremely unlikely).
GOALS
STUDENT SOLUTIONS (See G&J, p. 75-6 and the Appendix)