# 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 💡