Given a 3SAT problem with 3 binary variables (x1, x2, and x3), what is the min number of clauses that you would need to create an unsatisfiable sentence?
Create a 3SAT sentence with 3 binary variable that is not satisfiable using the minimum number of clauses identified in part 1.

Turn these in directly here in Canvas.

Part B -- Python's Itertools (3 points)

Python provides a powerful package called itertools (see this webpage for details: https://docs.python.org/3/library/itertools.html). This package provides an easy and memory efficient method of producing iterables that represent combination or permutations of items.

Construct a python program that uses the itertools function to print out all possible assignments of a 3 boolean variables. You will need to use the product function within itertools. If you need more help with the product function, look up itertools' documentation on the web.
Augment your python program so that it contains a function that accepts 3 variables (x1, x2, and x3). This function must return the truth value of the 3-SAT sentence you created in Part A:2 (should just be a return statement evaluating the expression). Call this function with all the possible settings and show that your sentence is indeed not satisfiable. In other words, if your function returns true, print the settings that produced a true answer, otherwise print a message verifying that it always returned false.
Create another function that is a copy of the one created in #2 but is missing one of the 3-SAT clauses. Using a similar for loop to #2, call this function with all possible settings of the boolean variables and print out the case where it finds a true assignment (a satisfying assignment).

Attach this program to this assignment, call it: cs412_np_3satcheck.py

Part C -- Practice Reduction (3 points)

Given the following 3-SAT sentence, construct the graph that would serve as input to the independent set problem.

(a\lor{b}\lor{c})\land(\lnot{a}\lor{b}\lor{c})\land(a\lor\lnot{b}\lor{c})\land(\lnot{a}\lor\lnot{b}\lor\lnot{c})

Draw this graph on a piece of paper and take a picture of it (and attach it to this assignment).
Write a brief (one sentence) description of the decision problem that needs to be solved by the independent set problem to show that this 3-SAT sentence has a valid assignment.
Identify the largest independent set in the graph created in step #1. If you select the variable "a" that is in the first clause, write that down as A1 (where the one identifies the clause that the variable came from). You can write this on your piece of paper with the graph (just make sure it is included in the picture) OR you can write it in the response section in Canvas.

Part D -- Prove that Independent Set is in NP (3 points)

Write a program that accepts a description of an undirected graph G and a list of vertices and verifies (in polynomial time) that the list of vertices is indeed an independent set).

Here is some example input:

The first line tells you how many vertices are in the graph G. The lines that follow contain the edge list for edge vertex. Finally, a proposed independent set is listed. Your program should output TRUE if the set listed in an independent set or FALSE if it is not an independent set (for example, 0 1 should not be an independent set).

Attached this program to this assignment and call it cs412_np_independent_set.py

Part E -- Show that Hamiltonian Paths are NP-Complete (3 points)

In this section, you need to construct the required components to show that finding a Hamiltonian path is NP-Complete (there are 3 components). Illustrate the reduction sequence as we did on the slides (as a picture) and using the <=p syntax and the boxes. Note: You do NOT need to show the steps required to change the input (the reduction), just the sketch of the order and what would need to be accomplished. For the other steps, write a sentence or two and if necessary, argue that these steps can be accomplished in polynomial time.

Submit these items in a section labels Part E in your writeup.

What and Where to Submit:

Submit the following 3 files here in Canvas:

cs412_np_3satcheck.py
cs412_np_independent_set.py
cs412_nplab.pdf