12
$\begingroup$

This is probably a stupid question, but I just don't understand. In another question they came up with Schaefer's dichotomy theorem. To me it looks like it proves that every CSP problem is either in P or in NP-complete, but not in between. Since every NP problem can be transformed in Polynomial time into CSP (because CSP is NP-complete), why does this not prove that there is no space between P and NP-Complete and so that P=NP?

For example my thoughts go like, Integer factorization can be rewritten as a satisfiability problem, so using Schaefer's theorem it should be either in P or NP-complete but not in between (even if we can't find out which one it is).

A different way to look at the entire question: Why can't we use Schaefer's theorem to decide whether integer factorization is in P or in NP-complete?

EDIT: in response to David Richerby's answer (it is too long for a comment):

Interesting, but I don't yet fully understand. When defining the set of relations gamma while using Schaefer's theorem, we may impose restrictions on it. For example, we may restrict gamma to use only relations of arity 2 (then the problem is in P). What kind of restrictions can we impose on gamma?

Why can't we impose such restrictions that all instances of CSP(gamma) are exactly the same as (isomorphic to?) L? For example, when transating Integer factorization for uneven numbers, one of the two divisors is binary represented as xn .. x3 x2 1. Now, I want this number to be greater than 1. So, I have the relation (xn or .. or x3 or x2). So I say that gamma can have an or-relation of arity n-1. But I don't want that or-relation to be used to include other instances than L in the language, so I furthermore impose that x2..xn in the or-relation are not allowed to have a negation. Of course, I also need to impose the restriction that only specific variables are used there.

Isn't it possible in this way to let CSP(gamma) be isomorphic to integer factorization? The main question is: what kind of restrictions may we impose on gamma?

EDIT 2: in response to Yuval Filmus' answer.

I understand your answer and it seems correct, though about the same as David's answer. For example, we may reduce factorization to 3-sat and then conclude that factorization is NP complete, which is wrong because 3-sat has other instances that are probably not factorization.

The part that I don't understand, is when an instance is (non-)arbitrary. For example, 2-SAT also seems non-arbitrary to me, because only clauses of arity 2 are allowed (although I must admit that the proof then still holds because it is an upper bound and in this case the upper bound is P).

Perhaps a better example is an NP-completeness one: the question linked above. One answerer gives a full Schaefer's proof. But I impose non-trivial restrictions on the input (2-SAT clauses are allowed and xor-clauses, but nothing else). Of course, the proof still holds because the CSP problems considered in the proof are exactly the same as the original one.

The part that I don't understand is why we can't do similar for factorization? Of course it's no use to reduce it to 3-SAT, but allow me to give the CSP instance that factorizes a number and only factorizes a number (of 4 bits). (skip to END-OF-SKIP if you believe this is possible).

Factorization instance.

INPUT:

(N=)$n_4n_3n_2n_1$ (the 4 bits of the number to factorize)
(M=)$m_4m_3m_2m_1$ (the 4 bits of the minimum value of the first divisor)

Now, let's transform this to a CSP instance

INPUT:
unary domains for $n_5..n_1$ and for $m_5..m_1$ (representing that N and M are given)

variables with domain {0,1}:
(D=)$d_4d_3d_2d_1$ (the first divisor)
(E=)$e_4e_3e_2e_1$ (the second divisor)

relations:

$e_4 \lor e_3 \lor e_2$ (representing E>1)

$(d_4 \land \neg m_4) \lor (d_4=m_4 \land d_3 \land \neg m_3) \lor (d_4=m_4 \land d_3=m_3 \land d_2 \land \neg m_2) \lor (d_4=m_4 \land d_3=m_3 \land d_2=m_2 \land d_1 \land \neg m_1)$
(representing D>M)

$d_1 \land e_1 = n_1$ (representing least significant bit multiplication)
$(d_1 \land e_2) \oplus (d_2 \land e_1) = n_2$ (representing the next bit multiplication)
$n_3 = ... ; n_4 = ...$

END-OF-SKIP

The crux is, when applying Schaefer's theorem, we must only consider such CSPs. (Just like for 2-SAT we only consider CSPs with arity 2). When doing that, either one of the six polymorphisms holds, or it does not (save some quirks in set theory). In either case, factorization is not NP-intermediate.

This can also be done for 3-SAT. Then, we should only consider (using the reduction) 3-SAT instances that represent factorization instances (which is not 3-SAT anymore).

Where do I go wrong?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ I strongly suggest that you read an exact formulation of Schaefer's dichotomy theorem. It is not true that you "may impose restrictions on [the set of relations]". Schaefer's dichotomy theorem doesn't cover this case. Wikipedia can sometimes be inaccurate and confusing, so I suggest you find lecture notes instead, or perhaps even look at a relevant paper. $\endgroup$ – Yuval Filmus May 14 '15 at 15:51
  • $\begingroup$ I didn't notice your comment before editing my answer. Maybe it's not allowed to impose restrictions on the set of relations, but it looks to me as if you should just not consider relations that don't match the restriction when applying Schaefer's theorem. Just like with 2-SAT, you don't consider relations that don't match the "restriction" that each clause should have 2 literals. $\endgroup$ – Albert Hendriks May 14 '15 at 23:33
  • 2
    $\begingroup$ There is a very formal notion of "restriction" which is used in Schaefer's theorem. The restriction "SAT instance which represents factorization" is not the type of restriction that Schaefer's theorem can handle. For every $\Gamma$ such that integer factorization can be represented as an instance of $\mathrm{CSP}(\Gamma)$, you will find that $\Gamma$ is such that solving $\mathrm{CSP}(\Gamma)$ is NP-complete. So Schaefer's theorem tells us absolutely nothing about the hardness of factorization (other than what we already know – that it is in NP). $\endgroup$ – Yuval Filmus May 15 '15 at 0:15
  • 3
    $\begingroup$ The fact that $\mathrm{CSP}(\Gamma)$ in the above comment is NP-complete doesn't mean that factorization itself is NP-complete, since the factorization instances have special structure, a type of structure that cannot be captured by Schaefer's theorem. $\endgroup$ – Yuval Filmus May 15 '15 at 0:17
  • 1
    $\begingroup$ btw does anyone know a good textbook or modern treatment of the Schaeffer dichotomy thm? $\endgroup$ – vzn May 15 '15 at 3:27
10
$\begingroup$

When you translate an arbitrary NP problem $L$ to CSP, you end up with some set of instances with some constraint language (set of relations) $\Gamma$. What Schaeffer's theorem says is that deciding all instances of CSP($\Gamma$) is either in P or is NP-complete. But, if you only need to decide some restricted set of instances (e.g., the instances you get by translating the problem $L$), it might be easier. In particular, if $L$ is NP-intermediate, then solving the corresponding instances of CSP($\Gamma$) would also be NP-intermediate – you could just translate the instances back to instances of $L$ and solve them there. But solving the class of all CSP($\Gamma$) instances would be NP-complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting. I edited my question in response to your answer. $\endgroup$ – Albert Hendriks May 14 '15 at 11:00
  • $\begingroup$ It's not restrictions on $\Gamma$ but restrictions on the input to the CSP that are significant, here. Saying "It's hard to solve all of CSP($\Gamma$)" isn't the same as "It's hard to solve the instances of CSP($\Gamma$) that you get by transforming, e.g., integer factorization instances." $\endgroup$ – David Richerby May 14 '15 at 11:08
  • $\begingroup$ I may be wrong, but I'd say that the input to the Integer factorization problem is the same as the input to CSP(gamma): any two binary numbers (the number to be factorized and the minimum value of one of the divisors). Right? I do understand the part that if you don't make the transformation carefully, you end up with a another problem. $\endgroup$ – Albert Hendriks May 14 '15 at 11:21
  • $\begingroup$ The input to the integer factorization is a pair of integers, as you say. The input to CSP($\Gamma$) is a set of variables that range over some domain and a set of $\Gamma$-constraints on those variables. The situation is just like, e.g., reducing 3-colourability to 3-SAT. The input to 3-colourability is a graph; the input to 3-SAT is a Boolean formula. $\endgroup$ – David Richerby May 14 '15 at 16:29
12
$\begingroup$

Schaefer's theorem covers a very specific situation: you are given a finite set $\Gamma$ of relations, and are interested in the complexity of $\mathrm{CSP}(\Gamma)$. Schaefer's theorem gives you an algorithm to decide whether this problem is NP-complete or in P. It doesn't cover any other situation.

When you translate a problem like integer factorization into a CSP, you will use a set of relations $\Gamma$ such that $\mathrm{CSP}(\Gamma)$ is NP-complete (this, given the common belief that integer factorization is not in P). But your instances are not arbitrary, so Schaefer's theorem only gives an upper bound on the complexity. It could well be that integer factorization is in fact not NP-complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your reply. I edited my question (EDIT 2) in response to your answer. $\endgroup$ – Albert Hendriks May 14 '15 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.