Extra problems on complexity

Prove that if a problem is in P, then it’s in NP. Give two proofs, one using the “certificate definition” of NP, and one using the “ND-algorithm definition”.

(Optional) Let p(x,y) be a polynomial in two variables, x and y, with integer coefficients.

1. Show the problem “Do there exist integers x and y such that p(x,y) = 0?” is in NP. Do this twice, once for each definition of NP.

2. Do you think the problem “Do there exist reals x and y such that p(x,y) = 0?” is in NP? Explain your reasoning.

Suppose X, Y, and Z are decision problems such that X is polynomial-time reducible to Y, and Y is polynomial-time reducible to Z. Is X necessarily polynomial-time reducible to Z? Why?

For each problem X listed below, state whether X is in P, in NP, or in both. For each affirmative claim, justify your answer; if you claim X is not in P (or NP), no explanation is necessary.

1. X: “Given a natural number n, is n a perfect square?” Input size: number of digits in n.

2. X: “Given natural numbers m and n, do there exist positive integers x, y, and z such that xm + yn = zm+n?” Input size: total number of digits in m and n. (Be careful!)

3. X: “Given n (not necessarily distinct) integers a_1, …, a_n, do there exist a_i₁, …, a_i₁₀ whose sum is 0?” Do this first assuming input size is n, and each addition or comparison between two integers is one step; then assuming input size is the total number of bits (binary digits) in all a_i, and each addition or comparison between two digits is one step.