gotchaModerate
Why does Schaefer's theorem not prove that P=NP?
Viewed 0 times
schaeferwhyprovethattheoremdoesnot
Problem
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
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
Solution
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.
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.
Context
StackExchange Computer Science Q#42544, answer score: 12
Revisions (0)
No revisions yet.