What is the definition of the class P?
What is the definition of the class NP?
What is the definition of a polynomial time reduction from set A to set B?
What is the definition of notation A ≤p B?
What is the definition of an NP-complete set?
Is the satisfiability problem known to be in NP, or only conjectured to be in NP?
Is the satisfiability problem known to be NP-complete, or only conjectured to be NP-complete?
Is it known whether the satisfiablity problem is in P?
Are there any computational problems that are neither in P nor in NP?
Is it possible for a problem to be in both P and NP?
Show that the problem of telling whether a number is composite is in NP. A number is composite if it is greater than 1 and not prime.
The Clique problem is
as follows.
Input. An undirected graph G and a positive integer K.
Question. Does there exist a set of K vertices in G such that,
if u and v are any two of those vertices,
then G has an edge from u to v?
Show that the Clique Problem is in NP.
Let A = {x | x is an even positive integer} and B = {x | x is a positive integer that is divisible by 3}. Integers can be arbitrarily large. Give a polynomial time reduction from A to B.
Two graphs are isomorphic if it is possible to assign numbers to the vertices of each so that, after the numbering, the edge sets of the two graphs are identical.
Here are two decision problems.
The Subgraph Isomorphism Problem (SIP)
Input. Two undirected graphs G and H.
Question. Is H isomorphic to a subgraph of G? That is,
can you get a graph that is isomorphic to H by deleting zero or
more edges and zero or more vertices from G?
The Hamilton Cycle Problem (HCP)
Input. An undirected graph G.
Question. Does G contain a simple cycle that includes all of its vertices?
That is, can you find a cycle in G, following the edges, that includes
every vertex exactly once? (Imagine doing a tour, where you start at a particular
vertex, tour through the vertices (following edges), and return to the start vertex,
where you are not allowed to return to a vertex that you have already visited,
except the start vertex at the end of the tour.)
Show that the HCP ≤p SIP by giving a polynomial-time reduction from HCP to SIP.