CS191 25 05 01
Zhu, Justin

CS191 25 05 01
Wed, May 1, 2019


Cook 1971

The difference between algebraic and exponential order is more crucial than the difference between finite and non-finite.

The seminal paper contains polynomial algebraic order solutions and the difference between exponential and polynomial time. Cook provides crucial definitions of polynomial-time reducibility between the different classes of problems.

Cook’s result created an unfinished search for an answer to the question of whether or not P = NP, forming the basis of complexity theory as we know it today.

Reduced means roughly that the first problem can be solved deterministically in polynomial time, a set of strings for example is bounded by the length of the string if one wants to find a certain character set.

These terms formed the basis of computational complexity for algorithms.

Karp 1972

Karp was a precocious child, interested in discrete mathematics.

Polynomial-bounded algorithms are important may just allow a collection of many polynomial-time algorithms. If P is defined as a class of language for a one-dimensional Turing machine, and NP is the class of languages recognizable in polynomial time by one-tape non-deterministic Turing machine.

Many different computational problems arise in mathematical programming, graph theory, combinatorics, computational logic, and switching theory. The way Karp formalized these problems are all complete and interestingly defined.

As a corollary,a large class of important computational problems involve the determination of properties of graphs, digraphs,integers, finite families of finite sets. The section lists a couple of problems solvable in polynomial time. The satisfiability of 2 literals per clause is the famous problem that sparked the birth of polynomial problems.