Skip to content
academia.sh
tr
Log in

Course Advanced

Theory of Computation

By the end of this course

Start course

01

Models of Computation

The languages finite automata can recognize, the limit production rules cross, the universal model, and the step budget's inadequacy in the face of undecidability.

  1. 01 Finite Automata Measuring the state budget by exhaustive count: in a universe of 31 strings, 1-state automata recognize 2 distinct languages, 2-state ones 26, 3-state ones 1054; against the 2-to-the-31 languages that could be written over that universe, this is a share of 0.0000004908.
  2. 02 Context-Free Languages Measuring languages the state budget cannot cover: the state count required for the equal-a's-and-b's language grows as 3, 5, 7, 9, 11 with the length limit, while a one-line production rule generates the same language exactly, and the rule's description never grows.
  3. 03 Turing Machine Measuring the tape model by exhaustive count: 9784 of 20,736 2-state, 2-symbol machines halt, the longest halting run takes 6 steps and the count does not change at all when the budget is raised from 6 to 200; of the 10,952 machines that do not halt, 5040 are settled by a loop certificate.
  4. 04 Undecidability Measuring that observation is not proof: on a one-line counter rule, 7 of 1000 starting points halt at budget 5, 1000 of 1000 at budget 200, but the same budget fails to settle 9 of 5000 starting points, and a starting point that fools every budget can be found.

02

Complexity Classes

Polynomial time, verifiability and certificates, transferring difficulty through reduction, the asymmetry of complement problems, an open question, and the measured deviation of approximate solutions.

  1. 01 Class P Measuring decision problems solvable in polynomial time under a finite step budget: on the same 20 examples, the threshold problem is decided in 12 steps, the pair problem in 66, while subset sum requires a budget of 10,000 steps. As input size rises from 8 to 20, the first two methods' worst-case steps go from 8 to 20 and from 28 to 190, while the third rises from 256 to 1,048,576. The difference between the decision problem class and the growth class from the Algorithms course is stated separately.
  2. 02 Class NP Establishing verifiability and the certificate concept in step counts: on 20 examples, solving spends 4321 steps, certificate verification 101, a ratio of 42.8. At a step budget of 13, 20 of 20 examples are decided with a certificate, while solving decides none. At input size 24, solving's worst case is 16,777,216 steps, verification 25. A certificate with one index dropped is rejected on 20 of 20 examples. The difference between this course's sense of "certificate" and the digital certificate sense in the Cryptography curriculum is stated separately.
  3. 03 NP-Complete and NP-Hard Measuring the transfer of difficulty through reduction, in step counts: the transformation that converts a subset sum example into a partition example takes 15 steps, 0.2632 of solving the source. On twenty examples, the reduction takes 300 steps, solving the source 4321, solving the target 19,847, and the two answers agree on 20 of 20 examples. At input size 24, the reduction stays at 27 steps while solving climbs to 16,777,216. What the direction of translation does and does not prove is stated separately.
  4. 04 co-NP and Relationships Between Classes The status of complement problems and the measured asymmetry between yes and no answers: on 20 examples, a yes certificate closes in 101 steps, while a no answer by exhaustive search needs 81,920. On structured no examples, a short 260-step proof works on 20 of 20; on unstructured examples, the same proof can say nothing on 20 of 20. At input size 24, the yes certificate takes 25 steps, the no proof 16,777,216. The threshold problem closes in 260 steps in both directions.
  5. 05 The P vs NP Question Stating the open question and laying out the only thing that can be measured: the known lower bound spends 240 steps, meet-in-the-middle 1357, exhaustive search 4321, and the two methods agree on 20 of 20 examples. At input size 24, the lower bound is 24, meet-in-the-middle 8192, exhaustive search 16,777,216; the gap's ratio runs from 341.3 to 699,050.7. At a budget of one million steps, exhaustive search reaches 19 numbers, meet-in-the-middle 37. The question is open, and no direction is claimed in this lesson.
  6. 06 Approximation and Heuristic Methods Counting the cost of giving up an exact solution, and the course's closing: the greedy approximation finds the exact result on 5 of 20 examples, diverges on 15, with a worst relative loss of 0.0676. As the exhaustively searched element count rises from 0 to 8, diverging examples drop from 15 to 0 and steps rise from 240 to 35,956; at k=12 the method spends 553,948 steps, exceeding the oracle's 81,920. The course closing carries a ten-row budget table and the closing of the Computer Science curriculum.

Start typing to search.

↑↓ ↵ Esc navigate · open · close