How would it be possible that primality testing is in P, but not factorization?
First of all, it doesn't make sense to talk about solving any particular formula in polynomial time--every specific formula can be solved in constant time (the answer is either yes or no, we just don't know which). So talking about whether any particular formula is &quot;evil&quot;, probably does not make sense.
Also, just because we can solve problem A, by reducing to the problem B, doesn't mean we can solve everything near problem B. In fact, we may not even be able to solve problem B, in some cases!
Can you remove some clauses and make a family of SAT problems harder? Definitely. Take any family, and add the clause $A \&amp; \bar{A} $. Now the answer is definitely &quot;no&quot;. Remove that clause, and the problem is hard.
This makes sense--removing constraints often feels like intuitively makes things harder. Think about sudoku--less filled in boxes, doesn't always make the problem easier.