CSE 100 Study Guide - Quiz Guide: Np-Hardness, Np-Completeness, Disjoint Sets

• School: UCSD
• Department: Computer Science & Engineering
• Course: CSE 100
• Professor: Nuno Bandeira

Document Summary

Any problem that can be solved in polynomial time. One can verify the answer for correctness in polynomial time. Only need to verify but do not necessarily need to be able to compute the correct answer in polynomial time. P is subset of np. because if we can solve a problem in polynomial time, then we can certainly verify a proposed answer to the problem in polynomial time. If it is at least as hard as the hardest problem in np. A problem h is np-hard when every problem l in np can be reduced , or transformed, to problem h in polynomial time. Np-hard problem is considered np-complete if it can be verified in polynomial time. The tsp optimization problem is np hard while tsp decision problem is np complete (which is also np hard). If given problem is not in class p, then must choose between two options.