Besides #3, this is the last remaining piece of Karp's 21 problems.
The classic reduction seems to be from SAT directly but we have already broken with this tradition already for other reductions.
Furthermore, we will need the reduction SAT <= 3-SAT anyway (see #5 ).
Besides #3, this is the last remaining piece of Karp's 21 problems. The classic reduction seems to be from SAT directly but we have already broken with this tradition already for other reductions. Furthermore, we will need the reduction
SAT <= 3-SATanyway (see #5 ).