Question

Show that for any problem $\prod _{}$ in NP, there is an algorithm which solves n in time O $\left(2^{p\left(n\right)}\right)$where is the size of the input instance and $\mathit{p}\left(n\right)$is a polynomial (which may depend on$\prod _{}$ ).

Short answer

The running time of the algorithm is as follows: $p\left(n\right)=\sum _{}^{p\left(n\right)}O\left(2^{p\left(n\right)}\right)$

Step-by-step solution

Introduction to the problem

An algorithm that solves the given problem in time O$\left(2^{p\left(n\right)}\right)$is as follows:

For every string that belongs to$\sum _{}^n$and accepted by the certifier, there is a polynomial time and a certificate that belongs to $\sum _{}^n$.

The time is $\left(C\left(s,t\right)\le p\left(n\right)\right)$.

Generate all the possible strings $\left(t\right)$and test whether $C\left(s,t\right)$is true under$p\left(n\right)$ steps.

Prove that there exist an algorithm to solve given problem

The set of strings is represented by $\prod _{}$.

Over an alphabet which is finite $\sum _{}^{}n$ nature, the string is called as the instance.

An algorithm decides a problem to be yes if belongs to$\prod _{}$ .

The algorithm will execute for polynomial time if for every string , the algorithm on will terminate with at-most $p\left(str\right)$steps.

The represents the polynomial time.

The running time of the algorithm is as follows:$p\left(n\right)=\sum _{}^{p\left(n\right)}O\left(2^{p\left(n\right)}\right)$