Problem Set 6—P and NP

Purpose

This problem set develops your understanding of the classes P and NP.

Background

This problem set is based on material covered in sections 34.1 and 34.2 of our textbook. We covered this material in classes on November 3 and November 10.

Activity

Solve each of the following problems.

Problem 1

Define the polynomial evaluation problem to be the decision problem whose input is a triple consisting of a polynomial, P, and two numbers, x and y; the input is to be accepted if and only if P(x) = y. Assume that numbers are encoded in a fixed-length encoding, and that a degree-n polynomial is represented as a list of its n+1 coefficients. Show that the polynomial evaluation problem is in P.

Problem 2

Exercise 34.2-1 in our textbook (show that graph isomorphism is in NP; see the exercise for a more precise description of the problem, and page 1171 for a definition of isomorphic graphs).

Problem 3

Prove that P is closed under complement, i.e., that if L is a language in P consisting of strings over some alphabet Σ, then the set L′ containing all strings over Σ that are not in L is also in P. This is a small part of Exercise 34.1-6 in our textbook.

Problem 4

Exercise 34.2-9 in our textbook (prove that P is a subset of co-NP; consider using the result from problem 3).

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.