Show that any language in NP has an algorithm that runs in t

Show that any language in NP has an algorithm that runs in time 2^O (n^k) for some k.

Solution

By the definition of the class NP: A language L belongs to NP if and only if there exist a two-input polynomial-time algorithm A and a constant c such that

L={x {0, 1} : there exists a certificate y with |y| = O(|x| c ) such that A(x, y) = 1}

Then algorithm A verifies L in polynomial time.

Therefore, for a language L in NP, we can design an algorithm A2 that decides L in time 2 O(n k ) for some constant k.

A2 for all possible y if A(x, y) == 1: return 1 return 0 There are 2 |y| possiblities of y. |y| = O(|x| c ), therefore there are 2 O(|x| c ) possibilities of y.

And for every y, the algorithm runs A(x,y) once, in polynomial time, O(|x| t ) for some constant t. So totally the runtime of the algorithm is 2 O(|x| c )O(|x| t ) = 2O(n c ) (c2 n t ) = 2O(n c ) (2log2c2+tlog2n) = 2 O(n k )