Efficient Algorithms

These come in three flavours:

  • $A$ is a deterministic polynomial-time algorithm if there exists a polynomial $P_A(\lambda)$ such that for all inputs $X$ of length $\lambda$, $TIME_A(X) \le P_A(\lambda)$.

  • A probabilistic strict polynomial-time algorithm $A$ has the same definition as above except that $A$ may flip coins.

  • A probabilistic expected polynomial-time algorithm $A$ has the same definition as above except $E[TIME_A(X)] \le P_A(\lambda)$.

Efficient Interactive Machines

As above, but running bounds should hold for all inputs and all input communication messages.

Negligible Functions

A function $f:\mathbb{Z}_{\ge 0}\rightarrow\mathbb{R}_{\ge 0}$ is negligible if for all $c \gt 0$, there exists a $\lambda_0 \gt 0$ such that for all $\lambda \ge \lambda_0$, $f(\lambda) \lt 1/\lambda^c$.

Example: $2^{-\lambda}, \lambda^{-log\lambda}$ are negligible, $\lambda^{-1000000} is nonnegligible$

[cf. Dan’s definition: A function $g(t) : \mathbb{Z}^+ \rightarrow \mathbb{R}^+$ is negligible if for all polynomials $h\in\mathbb{Z}^+[x]$ we have that $g(t)\lt 1/h(t)$ for sufficiently large $t$. ]