![]() |
NP-Hard Problems - Printable Version +- Free Academic Seminars And Projects Reports (https://easyreport.in) +-- Forum: Seminars Topics And Discussions (https://easyreport.in/forumdisplay.php?fid=30) +--- Forum: Miscellaneous Seminars Topics (https://easyreport.in/forumdisplay.php?fid=21) +---- Forum: General Seminar Topics (https://easyreport.in/forumdisplay.php?fid=58) +---- Thread: NP-Hard Problems (/showthread.php?tid=21201) |
NP-Hard Problems - priyababa - 08-16-2017 NP-Hard Problems [attachment=17993] Efficient Problems A generally-accepted minimum requirement for an algorithm to be considered efficient is that its running time is polynomial: O(nc) for some constant c, where n is the size of the input.1 Researchers recognized early on that not all problems can be solved this quickly, but we had a hard time figuring out exactly which ones could and which ones couldn t. there are several so-called NP-hard problems, which most people believe cannot be solved in polynomial time, even though nobody can prove a super-polynomial lower bound. P, NP, and co-NP A decision problem is a problem whose output is a single boolean value: YES or NO.2 Let me define three classes of decision problems: P is the set of decision problems that can be solved in polynomial time.3 Intuitively, P is the set of problems that can be solved quickly. NP is the set of decision problems with the following property: If the answer is YES, then there is a proof of this fact that can be checked in polynomial time. Intuitively, NP is the set of decision problems where we can verify a YES answer quickly if we have the solution in front of us. co-NP is the opposite of NP. If the answer to a problem in co-NP is NO, then there is a proof of this fact that can be checked in polynomial time. For example, the circuit satisfiability problem is in NP. If the answer is YES, then any set of m input values that produces TRUE output is a proof of this fact; we can check the proof by evaluating the circuit in polynomial time. It is widely believed that circuit satisfiability is not in P or in co-NP, but nobody actually knows. 21.4 Reductions and SAT To prove that a problem is NP-hard, we use a reduction argument. Reducing problem A to another problem B means describing an algorithm to solve problem A under the assumption that an algorithm for problem B already exists. You re already used to doing reductions, only you probably call it something else, like writing subroutines or utility functions, or modular programming. To prove something is NP-hard, we describe a similar transformation between problems, but not in the direction that most people expect. You should tattoo the following rule of onto the back of your hand. Maximum Independent (from 3SAT) For the next few problems we consider, the input is a simple, unweighted graph, and the problem asks for the size of the largest or smallest subgraph satisfying some structural property. Let G be an arbitrary graph. An independent set in G is a subset of the vertices of G with no edges between them. The maximum independent set problem, or simply MAXINDSET, asks for the size of the largest independent set in a given graph. |