למה התשובה היא רק א? למה הרדוקציה בב' לא נכונה, הרי IP היא NP קשה וכך גם 3DNF, לא?
Date: 02 Jul 2011 15:27
Number of posts: 2
RSS: New posts
nop … 3DNF is P, since you need to satisfy only 1 clause, which has 3 literals.
you can make polynomial reduction from P to NPC since P is in NP
but you cannot make polynomial reduction from NPC to P, since each L in NPC is also in NPhard, and there is no polynomial reduction from NPhard to P