Question

For each of the following problems, indicate which are in P and which are in NP. For
those you think are in P, give an outline of the algorithm to solve them. For those you think are
in NP, explain why you think they are not solvable in polynomial time. (Hint: think about an
algorithm to solve these problems, and then determine if it is polynomial.)
a. The Smarandache function, S(k), gives the smallest integer m, so that m! can be evenly
divided by k. For example, S(9) = 6 because 6!=720 and 9 does not divide any smaller
factorial. Calculate the Smarandache function for any number.
b. You have to seat N children in the smallest number of rows in an auditorium. For each
child, you have a list of who that child dislikes. Experience shows that if a child is in the
same row or any row behind a child that he or she dislikes, he or she will throw things at
the other child. Given this list, determine in which row to seat each child, or determine
that they cannot be seated.
c. You are in front of a wall that stretches infinitely in both directions. You know that there
is a door in the wall, but it is dark, and you have only a dim flashlight that allows you to
see no more than one step in either direction. Find the door.

Answer 1

Solution 1: It is a NP, this problem cannot be solved in a polynomial time because for the factorials of very large numbers the problem would require exponential amount of time to solve it.

Solution 2: It is a P, this problem can be solved in a Polynomial amount of time. Although it is a complex problem but the careful scheduling might lead to the solution of the problem in polynomial time.

SOlution 3: It is clearly a NP, since the wall is infinitely long and its midnight, therefore either the agent would be able to find the door right away or he/she can just keep looking for it all their life.