On Independent Sets, 2 -to- 2 Games and Grassmann Graphs

摘要

We present a candidate reduction from the 3 -Lin problem to the 2 -to- 2 Games problem and present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. A reduction that is sound in this non-standard sense implies that it is NP-hard to distinguish whether an n -vertex graph has an independent set of size 1 ? 1 2 n ? o ( n ) or whether every independent set has size o ( n ) , and consequently, that it is NP-hard to approximate the Vertex Cover problem within a factor 2 ? o (1)