When Dr. Krys was an undergraduate (which, by his account, could not have been as long ago as it must have been), he realized that the DNF-Satisfiability problem has a polynomial time solution. He even wrote a little program that could solve the problem, and it was fast! Even with thousands of clauses using thousands of variables, it could still produce a satisfying assignment and/or verify that there was no such assignment in very little time. Even better, he realized that he could convert CNF-Satisfiability problems into DNF-Satisfiability problems! So now, try your hand at his analysis and answer the following:
Write a formal statement of the DNF-Satisfiability problem as a decision problem.
What is the polynomial time solution to the DNF-Satisfiability problem? Write out the algorithm; prove its runtime and prove that it works.
Prove that you can convert a CNF-Satisfiability problem to DNF-Satisfiability.
Why is Dr. krys still teaching for a living instead of enjoying his million dollar prize? (Be sure to rigorously prove your answer.)
2/An independent set of a graph G=(V,E) is a subset of vertices V’ such that each edge in E is incident on at most one vertex in V’. The independent-set problem is to find a maximum-size independent set in G. Formulate a decision problem statement of the independent set problem and prove that it is NP-Complete. (HINT: Think about it until something “clicks”). [This problem is adapted from Introduction to Algorithms 3rd Edition by Thomas H. Cormen et. Al]
Last Completed Projects
| topic title | academic level | Writer | delivered |
|---|