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