Hard 3SAT is known as an NP-complete problem. Very hard:no polynomial algorithm is known. Conjecture:no polynomial algorithm exists. If a polynomial algorithm exists for 3SAT,then polynomial algorithms exist for all NP problems. More details in last lecture. 5Hard ◼ 3SAT is known as an NP-complete problem. ❑ Very hard: no polynomial algorithm is known. ❑ Conjecture: no polynomial algorithm exists. ❑ If a polynomial algorithm exists for 3SAT, then polynomial algorithms exist for all NP problems. ◼ More details in last lecture. 5