tailieunhanh - Đề tài " On the hardness of approximating minimum vertex cover "

We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of , extending on previous PCP and hardness of approximation technique. To that end, one needs to develop a new proof framework, and to borrow and extend ideas from several fields. 1. Introduction The basic purpose of computational complexity theory is to classify computational problems according to the amount of resources required to solve them. In particular, the most basic task is to classify computational problems to those that are efficiently solvable and those that are not. . | Annals of Mathematics On the hardness of approximating minimum vertex cover By Irit Dinur and Samuel Safra Annals of Mathematics 162 2005 439 485 On the hardness of approximating minimum vertex cover By Irit Dinur and Samuel Safra Abstract We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of extending on previous PCP and hardness of approximation technique. To that end one needs to develop a new proof framework and to borrow and extend ideas from several fields. 1. Introduction The basic purpose of computational complexity theory is to classify computational problems according to the amount of resources required to solve them. In particular the most basic task is to classify computational problems to those that are efficiently solvable and those that are not. The complexity class P consists of all problems that can be solved in polynomial-time. It is considered for this rough classification as the class of efficiently solvable problems. While many computational problems are known to be in P many others are neither known to be in P nor proven to be outside P. Indeed many such problems are known to be in the class NP namely the class of all problems whose solutions can be verified in polynomial-time. When it comes to proving that a problem is outside a certain complexity class current techniques are radically inadequate. The most fundamental open question of complexity theory namely the P vs. NP question may be a particular instance of this shortcoming. While the P vs. NP question is wide open one may still classify computational problems into those in P and those that are NP-hard Coo71 Lev73 Kar72 . A computational problem L is NP-hard if its complexity epitomizes the hardness of NP. That is any NP problem can be efficiently reduced to L. Thus the existence of a polynomial-time solution for L implies P NP. Consequently showing P NP would immediately rule out an efficient algorithm Research supported in part by the Fund