Consider Search problem Input array of integers A a1 an in

Consider \"Search problem\": Input: array of integers A = [a_1, ..., a_n], integer b Question: is it true that A contains b? Show, that \"Search problem\" elementof NP. Explain each step of the proof

Solution

If we prove that the given \"Search Problem\" belongs to P, we can show that \"Search Problem\" also belongs to NP, as we know that \"All problems in P, also belong in NP\"

Now we are left with problem to prove that Search Problem can be solved in polynomial time, using an algorithm, which is quite simple. We propose an algorithm for the problem, and show its time complexity is linear. Now if we have the algorithm, it is guaranteed to be deterministic ( by definition of algorithm ). So lets give an algorithm for the problem and we are done:

search_problem( A, b ):

for element in A :

if element == b:

return true;

return false;

Clearly this is linear in size of input array. Thus we are done :)