0
$\begingroup$

Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally "evil" (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 "Primes is in P". The satisfiability of this formula cannot be "evil", 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 "we don't know" 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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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 "evil", 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 \& \bar{A} $. Now the answer is definitely "no". 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Further to the first point, for any "hard" instance of SAT, there is an algorithm which solves it in linear time. You need linear time because you need to look at the whole input: if (this_the_difficult_instance) { output(predetermined_solution); } else { run_normal_sat_solver(); } $\endgroup$
    – Pseudonym ♦
    Commented Oct 12, 2020 at 4:22
  • $\begingroup$ When I talk about "solving", I mean solving by a computer/TM that doesn't already know the answer obviously. Which is the big yes/no question with unproven answer. Thank you for the counterexamples, I don't know why I couldn't think of it that way. $\endgroup$
    – user102180
    Commented Oct 12, 2020 at 4:26
1
$\begingroup$

"Primality testing can be reduced to the satisfiability of a multiplication circuit" - that's right, or close enough, because it can be reduced to the non-satisfiabilty of a multiplication circuit.

However, factoring cannot be reduced to the satisfiability of a multiplication circuit. It can be reduced to actually satisfying the circuit. Proving or disproving satisfiability, and finding an actual way to satisfy the formula are totally different in difficulty.

"How can this be" - for an example, go back to high school maths. Every continuous function of real numbers on a closed interval has a maximum and a minimum. And if f(a) < 0 and f(b) > 0 then the function has a root on the interval [a, b]. But finding the maximum, minimum, and root, that's a totally different matter.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.