04 Polynomial Time

Definition

We say that an algorithm $A(x)$ ($x$ is input) decides a predicate/language $L\subseteq \{0,1{\}}^{\star }$ in O(f(n)) if, for each instance $x\in \{0,1{\}}^{\star }$, $A(x)$ terminates after $O(f(|x|))$ basic steps of computation and accepts if and only if $x\in L$.

(We can also speak of solving a problem in time $O(f(n))$.)
From here, polynomial-time computation is defined as expected:

Definition

$\mathbf{P}$ is the set of $L\subseteq \{0,1{\}}^{\star }$ such that there is some olynomial $p(n)$ and an algorithm $A(x)$ deciding $L$ in $O(p(n))$ steps.

Example: Satisfiability Revisited

Eval Problem: $\{(A,\alpha ):\alpha (A)=1\}$
By earlier $O(n)$-time algorithm:
$\text{Eval}\in P$

SAT Problem: $\text{SAT}\in ?P$

Example: Reachability

$G=(V,E\subseteq V\times V)$ (meaning: A graph $G$ consists of a set of vertices $V$ and a set of edges $E$, where each edge is an ordered pair of vertices).
Reach = $\{(G,s\in V,t\in V:\text{there is a path from s to t in G}\}$
Algorithm : Calculate $E^1,E^2,E^3,\cdots$ progressively where $E^i$ is the graph of $i$-reachability. Then $s$ reaches $t$ iff $(s,t)\in E_{|v|}$
$\therefore \text{Reach}\in P$