CSC427 Spring 2018, HW #8
Mitsu Ogihara
Due date: Wednesday, April 17
- (15 points) A positive integer n ≥ 2 is a prime number if and only if there is no integer d,2≤d≤n−1,suchthatddividesn. Showthatthelanguage{0p |pisaprime number } is in class P.
- (15 points) It is known that an odd number n is a prime number if and only there exists an integer a, 2 ≤ a ≤ n−1, such that a(n−1)/2 mod n is n−1 and a(n−1) mod n is 1, where mod n is the remainder function divided by n. Show that using this property, {n | n is a binary representation of an odd prime number } is in class P
- Let G be any directed graph. We say that two nodes s and t of G are strongly connected in G if there is a directed path from s to t as well as there is a directed path from t to s. Let sRGt denote the property that s and t are strongly connected in G.
(a) (10 points) Show that RG is an equivalence relation.
(b) (15 points) Show the language {⟨G, s, t⟩ | s and t are strongly connected in G} isin class P
- (15 points) Let H be the set of all graphs that contain a four-node clique. Prove that
H is in class P.
- (15 points) Let H be the language {⟨f(x),k⟩ | f(x) is some polynomial of integer coefficients, k is an integer, such that f(x) has an integer root between −k and k }, where the degree of f, the coefficients of f, and k are all given in binary. Show that H is class NP.
- (15 points) Let Λ be some list of positive integers, say [a1, . . . , am]. We say that Λ is splittable if there is a sublist [ai1 , . . . , aik ] such that the sum ai1 +· · ·+aik is exactly one half of a1 +···+am (if the sum a1 +···+am is an odd number, there Λ is not trivially splittable). Define the language A = {⟨Λ⟩ | Λ is splittable }, where the elements of the list Λ are encoded in binary. Show that A is class NP.
1