Homework 4 - due 3/30/2016

In this assignment, a code to calculate satisfiability in a circuit will be transformed to work with OpenMP.

What is satisfiability? The full name is Boolean Satisfiability Problem (SAT). Given a equation or formula that has boolean inputs (TRUE or FALSE), is there some combination of the inputs where the equation evaluates to TRUE. SAT is one of the first problems that was proven to be NP-complete

A C code, sats.c, checks all 2^16 combinations of inputs to a circuit to find the few where the circuit has an output of TRUE. 

> ./a.out
39413) 1010111110011001
39414) 0110111110011001
39415) 1110111110011001
39925) 1010111111011001
39926) 0110111111011001
39927) 1110111111011001
40437) 1010111110111001
40438) 0110111110111001
40439) 1110111110111001
Done

Take this code and rewrite it to use OpenMP. It is your decision whether to divide the loop in main() into chunks or to use threads in the function check_circuit().

As is, the code evaluates all the combinations very fast. You should rewrite it to have a more complex circuit with maybe 2^24 inputs (any power greater than 16 is acceptable) to determine whether a speedup occurs with using OpenMP. To increase the size of the circuit, the number of elements in the array has to increased as well as add more combinations of the elements.