]> Cryptography - Asymptotic Complexity

Efficient Algorithms

These come in three flavours:

• $A$ is a deterministic polynomial-time algorithm if there exists a polynomial ${P}_{A}\left(\lambda \right)$ such that for all inputs $X$ of length $\lambda$, ${\mathrm{TIME}}_{A}\left(X\right)\le {P}_{A}\left(\lambda \right)$.

• 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\left[{\mathrm{TIME}}_{A}\left(X\right)\right]\le {P}_{A}\left(\lambda \right)$.

Efficient Interactive Machines

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

Negligible Functions

A function $f:{ℤ}_{\ge 0}\to {ℝ}_{\ge 0}$ is negligible if for all $c>0$, there exists a ${\lambda }_{0}>0$ such that for all $\lambda \ge {\lambda }_{0}$, $f\left(\lambda \right)<1/{\lambda }^{c}$.

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

[cf. Dan's definition: A function $g\left(t\right):{ℤ}^{+}\to {ℝ}^{+}$ is negligible if for all polynomials $h\in {ℤ}^{+}\left[x\right]$ we have that $g\left(t\right)<1/h\left(t\right)$ for sufficiently large $t$. ]