What would we prove about complexity classes if we discovered a polynomial time algorithm for finding satisfying truth assignments to 3SAT problems?
3SAT is an NP-complete problem, hence we have a polynomial time algorithm for solving an NP complete problem, hence P and NP would be the same class of problem.
Comments
No comments have yet been made