CS6515 EXAM 3 STUDY GUIDE EXAM QUESTIONS AND ANSWERS

CS6515 EXAM 3 STUDY GUIDE EXAM QUESTIONS AND
ANSWERS
What is a P problem? - CORRECT ANSWER✅✅P = Polynomial

-A problem that can be solved in Polynomial time.

-There is a Polynomial time algorithm to solve it.



What is a NP problem? - CORRECT ANSWER✅✅NP = Non-Deterministically Polynomial

-A problem where the Solution can be VERIFIED in Polynomial-Time



What are differences in P and NP? - CORRECT ANSWER✅✅All P problems are in NP but all NP problems
are not in P. P is a subset of NP.

-Problems may be verifiable in Polynomial-Time but not solvable in Polynomial-Time



What are NP-Complete Problems? - CORRECT ANSWER✅✅The hardest problems in the NP class.

A problem is NP-Complete if it is in NP and in NP-Hard.



What are NP-Hard problems? - CORRECT ANSWER✅✅A problem at least as hard as every problem in
the class NP.

A problem is NP-Hard if all other problems in NP can be polynomially reduced to it.

NP-Hard problems don't have to be NP problems.



What is the difference between NP-Complete and NP-Hard? - CORRECT ANSWER✅✅NP-Complete
problems are the hardest in the set NP.

NP-Hard is not necessarily in NP.

NP-Hard problems are at least as hard as everything in the set NP.



What is a clause edge? - CORRECT ANSWER✅✅An edge between vertices in the same clause



What is a variable edge? - CORRECT ANSWER✅✅An edge between complimentary vertices