NP and Language Decidability

Today I am going to attempt solving another exercise related to the study of NP problems and languages.
--------------------------------
Problem:
Show that any language in NP can be decided by an algorithm running in time 2^(O(n^k)) for some constant k.


--------------------------------
Solution:
Let's start by observing that:
A language L is decided by an algorithm A if x ∈ A entails A(x) = 1 and x ∉ L entails A(x) = 0.

and observing that:
A language L belongs to NP if and only if there exists 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}

Having remembered what language decidability and NP means, we can go ahead and solve the problem in question.


From this observations we can see that for each language L in NP, there is an algorithm A that can verify each item x in L in polynomial time, given a certificate y with length O(|x|^c).


To decide if a given x ∈ {0, 1}* is part of a given language L ∈ NP, we need to determine if there is a certificate y of length O(|x|^c) such that the accepting algorithm A can verify if A(x, y) = 1 or not. To decide if such certificate y exists we need to try all possible y ∈ {0, 1}* with |y| = O(|x|^c) and evaluate A(x, y) for it. After evaluating all 2^|y| possible certificates with A(x, y) we can determine for sure if there exists a certificate y for which A(x, y) = 1 for the given x.
Hence there exists an algorithm A' that decides any language in NP in 2^O(n^k) with k constant.


For a given language L and its accepting algorithm A, this algorithm A' looks something like this:
A'(x) = for each y∈ {0, 1}* with |y| = O(|x|^c)
                  if (A(x, y) == 1) then return 1;
            return 0;
//and it runs in worst-case time of 2^O(|x|^c).
QED?