University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

CSC 456/656 Assignment 9

Due date: Thursday, May 1, 2014, 4:00 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
  1. Consider the Boolean expresssion:
    x1⇒x2⋅∼x1 (That's "implies" not "equal.")
    1. Convert that expression to an equisatisfiable Boolean expression in 3-CNF form, using the parse tree method we did in class. (When I did it, I got a 3-CNF expression with nine clauses.) Actually, I am not sure it was nine exactly.
    2. Find a satisfying assignment of the original Boolean expression, and give a corresponding satisying assignment of the 3-CNF expression.
  2. Consider the 3-CNF expression:
    (x1+x2+x3)⋅(∼x1+∼x2+x4)⋅(∼x3+x4+∼x2)
    1. The reduction we did in class maps that expression to an instance of the k-independent set problem. Draw the graph for that instance, and state the value of k.
    2. Select a k-independent set of nodes of that graph, and give a corresponding satisfying assignment of the Boolean expression.
  3. Prove that integer factorization is in both NP and co-NP. (You will need to use the result that primality is in P, which was first proved in 2002 by Agrawal, Kayal, and Saxena.) Do not be ashamed to go to the internet, but write the proof in your own words and your own handwriting.

Assignment 9 is now finished.

Back to Course Page