]> Cryptography - Asymptotic Complexity

Efficient Algorithms

These come in three flavours:

  • A is a deterministic polynomial-time algorithm if there exists a polynomial P A(λ) such that for all inputs X of length λ, TIME A(X)P A(λ).

  • 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)]P A(λ).

Efficient Interactive Machines

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

Negligible Functions

A function f: 0 0 is negligible if for all c>0 , there exists a λ 0 >0 such that for all λλ 0 , f(λ)<1 /λ c.

Example: 2 λ,λ logλ are negligible, λ 1000000 isnonnegligible

[cf. Dan's definition: A function g(t): + + is negligible if for all polynomials h +[x] we have that g(t)<1 /h(t) for sufficiently large t. ]