In: Computer Science
Exercise 5 (1 pt for each correct answer)
For each of the following statements indicate whether it is true, false, or unknown.
Bonus exercise (2 pts)
Show that if P=NP then there is a polynomial-time algorithm for the following search problem: given a graph, find its largest clique.
1.The SAT problem is in P.
ans:- False
2.The SAT problem is in NP.
ans:-True
3.The SAT problem is in EXP
ans:-True
SAT is the first problem that was proven to be NP-complete by Cook's Theorem.
It is possible to determine whether a boolean expression is satisfiable, the question is how quickly it can be done.
If there are n variables, then we can try all 2^n possible truth assignments, and eventually we'll find if there is a satisfying one, but this is not polynomial time with respect to the size of the input.
There might be some polynomial time algorithm that does solve SAT, we don't know, however SAT is NP-complete, which gives strong evidence that there isn't a polynomial time algorithm that's why SAT is not in P and it is rather in NP.
Since the SAT problem is NP-complete, only algorithms with exponential worst-case complexity are known for it.
So, if they can be solved then they would be solved in worst case as exponential algorithm.