How would it be possible that primality testing is in P, but not factorization? Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally &quot;evil&quot; (i.e, the satisfiability can be exponentially hard to determine in the size of the formula).
Primality testing can be reduced to the satisfiability of a multiplication circuit, which can be reduced to the satisfiability of a 3SAT formula. But &quot;Primes is in P&quot;. The satisfiability of this formula cannot be &quot;evil&quot;, since it can be reduced to AKS primality test for example.
Integer factorization can be achieved by finding a satisfying assignment to the same formula. This can be achieved by choosing a variable, and then testing the satisfiability again. Choosing a variable, simplifies the formula through unit propagation. The new formula is a subset of the previous one. Now suddenly &quot;we don't know&quot; whether this formula can be solved in polynomial time.
Isn't this a contradiction? Is it possible that the subset of a formula is harder to solve than the formula itself?
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.