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?