Re: 2 true/false NP complexity related questions


#2 would be true if you replaced "X <=p SAT" by "SAT <=p X" for the reasons
that you state, but as it stands it is false because the reduction goes in
the wrong direction.

Yes, you need to replace the reduction by SAT <= p X, and the reason
for that is that if you reduce X <= p SAT, you just gave an
exponential time
algorithm for the problem X, which might not require one.
(e.g. sorting by enumerating all permutations)

.

Relevant Pages

  • Re: Infinite Number of Cities
    ... What I'm "on about," is that as a matter of reduction to practice, ... The number of generatable combinations and permutations on modern ...
    (comp.sys.ibm.pc.games.rpg)
  • Re: Lower bound analysis, question
    ... Ahhhh, of course, a reduction from sorting to inserting n items in the ... datastructure and then removing them all, placing them in ascending order in ...
    (comp.theory)
  • Re: Lower bound analysis, question
    ... he must have meant removeMin instead of findMin. ... The solution must then be a reduction from sorting to inserting n items in ... implicitly result in a comparison based sorting algorithm faster than n*log ...
    (comp.programming)