Comment by caughtinthought
16 hours ago
Basically 3SAT algo isn't sub-exponential enough to absorb the arbitrary poly cost for the reduction
So 3SAT+poly reduction ends up being exponential
16 hours ago
Basically 3SAT algo isn't sub-exponential enough to absorb the arbitrary poly cost for the reduction
So 3SAT+poly reduction ends up being exponential
Gotcha, thanks