Asymptotic Complexity

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\). ]


Ben Lynn blynn@cs.stanford.edu 💡