<p>And one way of trying to solve such a problem is to do a form of backtracking, or what is also called "branch-and-bound". (Sorry, this was too long for a comment.)</p>

<p>Here's one possible heuristic: </p>

<p>(1) Choose some variable $x$ that is "most" constrained in some sense (maybe it occurs the most often). Suppose its integer range is $[L,R]$, and let $M$ be the midpoint of that interval. Now try to recursively solve the problem when $x &lt; M$ is assumed, and separately when $x \geq M$. </p>

<p>(2) In each recursive call, relax the predicate to be a linear program (i.e., the solutions to the variables are over the rationals), and include all range constraints such as $x \geq L$ and $x \leq R$. Check if the resulting linear program is still feasible over the rationals. If it isn't feasible over the rationals, then it won't be feasible over the integers either, so you can stop and backtrack. If it is feasible over the rationals, continue with step (1). </p>

<p>Note: not all possible constraints (e.g. quadratic polynomials like $x(1-x) = 0$) can be neatly expressed as linear constraints; one possible "solution" to this is to simply leave those constraints out (or, replace these "hard" constraints with linear constraints that are consequences of the hard constraint being true... for example, $x(1-x)=0$ has the consequence that $x \geq 0$ and $x \leq 1$).</p>

<p>That's about as much detail as a CS theory site can give you ;)</p>

CC BY-SA 2.5
2010-09-11T03:10:58.293Z
But if this problem is NP-hard, then your heuristic isn't going to work so well for some instances, no? :)  It also seems that by relaxing the constraints with terms like x(1-x), you're getting rid of the very parts that make the problem interesting!
Kurt
CC BY-SA 2.5
2010-09-11T22:46:40.943Z
Of course it won't always work... that's why I called it a "heuristic" :) By the way, I think this kind of relaxation to linear programming is quite standard, but I don't remember where I first read about it.
Ryan Williams
CC BY-SA 2.5
2010-09-12T11:21:58.710Z
To allow reader to find more about it, this method is called “branch-and-bound.”
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-13T04:02:24.933Z
I do not immediately see why the problem is reducible to 3sat (without a huge blowup to the given instance). The intervals the variables are contained inside might be very large. No?
Sariel Har-Peled
CC BY-SA 2.5
2010-09-13T04:21:41.227Z
If the interval endpoints are specified in binary along with the input, as well as the number of bits of precision (in unary), then the problem is in $NP$, and hence reducible to 3sat. If the precision is specified in binary then one runs into trouble.
Ryan Williams
CC BY-SA 2.5
2010-09-10T18:31:14.027Z
2010-09-12T16:34:46.313Z
2010-09-12T16:34:46.313Z
Ryan Williams
<p>Consider a variant of a satisifiability problem.</p>

<ul>
<li><p>Given n dimensions (n >= 3, <strike>n &lt; 10,000</strike> <i>think of n as large but finite</i>)</p></li>
<li><p>The range of each dimension is either an interval over the integers or an interval over the fixed-point decimals (which can be mapped to be the integers).</p></li>
<li><p>Given a truth predicate which can use these operations:</p></li>
</ul>

<blockquote>
  <p>(&lt;, =>, ==, !=, *, +, -, /, if/then, and}</p>
</blockquote>

<p>Example in Prolog of a predicate of truth:</p>

<pre><code>Predicate(V1, V2, V3) :-
   V2 =&lt; V3,
   V1 * 5 =&lt; V3,
   V1 * 50 &gt;= V3.
</code></pre>

<ul>
<li>Is this mappable to 3SAT?</li>
<li>Is this less hard than 3SAT?</li>
<li>What are pragmatic and efficient solutions to select some true point (or set of points) in the space?</li>
</ul>

CC BY-SA 2.5
2010-09-10T18:22:39.007Z
This problem is certainly reducible to 3SAT, and it is as hard as 3SAT. Require that every variable of the 3SAT formula $x_i$ is in the integer range $[0,1]$. Given a clause $(x_1 \vee x_2 \vee x_3)$, add the constraint $x_1 + x_2 + x_3 >= 0$ in your predicate.
Ryan Williams
CC BY-SA 2.5
2010-09-10T18:26:57.690Z
Seems like the set of all tuples (V1, V2, ..., Vn) is bounded above by a constant. So not sure what you are trying to ask here.
Aryabhata
CC BY-SA 2.5
2010-09-10T18:34:24.190Z
@Moron, the number of all possible satisfying assignments to a Boolean formula is also bounded above by a constant, $2^n$...
Ryan Williams
CC BY-SA 2.5
2010-09-10T18:36:32.673Z
@Ryan: The number of variables is fixed here (n < 10000). The range of each variable is fixed too, hence my comment. $2^n$ is not really constant if $n$ isn't :-)
Aryabhata
CC BY-SA 2.5
2010-09-10T18:45:02.797Z
@Moron: I took "10,000" to mean "essentially unbounded". The reply "$2^{10,000}$ is constant" is not helpful.
Ryan Williams
CC BY-SA 2.5
2010-09-10T18:51:05.230Z
@Ryan: Well, asking if it is harder than 3SAT does not make too much sense, theoretically speaking. This is supposed to be a high level TCS exchange site after all. If the comment will help clarify the question, why isn't it helpful? It was just a _comment_, intented to clarify the question, and not to give an answer.
Aryabhata
CC BY-SA 2.5
2010-09-10T18:58:45.463Z
@Moron: I think it is quite clear what is being asked.
Ryan Williams
CC BY-SA 2.5
2010-09-10T19:07:04.100Z
@Ryan: I disagree. If it is possible the clarify the question exactly, why not? Perhaps it will also help clarify any confusion that might exist in Paul's mind.
Aryabhata
CC BY-SA 2.5
2010-09-10T19:39:34.677Z
@Ryan, @Moron: The intervals and the number of dimensions are *finite but large*. I am uncertain if the ability to have the less-than operator weakens the situation from the 'hardness' of N-SAT.
Paul Nathan
CC BY-SA 2.5
2010-09-10T20:40:32.200Z
@Paul: thanks, I have lightly edited your question to reflect this.
Ryan Williams
CC BY-SA 2.5
2010-09-10T20:44:26.503Z
It is difficult to distinguish between “bounded and reasonably small” and “bounded but can be very large” in complexity theory.  A usual way to cope with this is to pretend the latter to be unbounded.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-10T21:02:13.840Z
@Paul: Note you can also prove hardness with $=$, not just $\geq$. Instead of $x_1 + x_2 + x_3 \geq 0$, use $(1-x_1)*(1-x_2)*(1-x_3)=0$.
Ryan Williams
CC BY-SA 2.5
2010-09-11T03:30:31.887Z
@Paul: The list of operands you can use inside a predicate does not include "and", but you're using the comma as if it were an "and".  Should we consider "and" to be allowable in the definition of a predicate?
Kurt
CC BY-SA 2.5
2010-09-13T16:36:16.657Z
@Kurt: My bad. Yes. Commas in Prolog are indeed `and`.
Paul Nathan
<cc.complexity-theory><sat>
Is this problem mappable to 3SAT or is it weaker than 3SAT?
Paul Nathan
# Is this problem mappable to 3SAT or is it weaker than 3SAT?

(Asked by: username_0 on 2010-09-10)

Consider a variant of a satisifiability problem.

Given n dimensions (n >= 3, n < 10,000 think of n as large but finite)
The range of each dimension is either an interval over the integers or an interval over the fixed-point decimals (which can be mapped to be the integers).
Given a truth predicate which can use these operations:


(<, =>, ==, !=, *, +, -, /, if/then, and}

Example in Prolog of a predicate of truth:
Predicate(V1, V2, V3) :-
   V2 =< V3,
   V1 * 5 =< V3,
   V1 * 50 >= V3.


Is this mappable to 3SAT?
Is this less hard than 3SAT?
What are pragmatic and efficient solutions to select some true point (or set of points) in the space?

**Tags:** cc.complexity-theory, sat
> **Comments:**
> **username_1**: This problem is certainly reducible to 3SAT, and it is as hard as 3SAT. Require that every variable of the 3SAT formula $x_i$ is in the integer range $[0,1]$. Given a clause $(x_1 \vee x_2 \vee x_3)$, add the constraint $x_1 + x_2 + x_3 >= 0$ in your predicate.  
> **username_2**: Seems like the set of all tuples (V1, V2, ..., Vn) is bounded above by a constant. So not sure what you are trying to ask here.  
> **username_1**: @Moron, the number of all possible satisfying assignments to a Boolean formula is also bounded above by a constant, $2^n$...  
> **username_2**: @Ryan: The number of variables is fixed here (n < 10000). The range of each variable is fixed too, hence my comment. $2^n$ is not really constant if $n$ isn't :-)  
> **username_1**: @Moron: I took "10,000" to mean "essentially unbounded". The reply "$2^{10,000}$ is constant" is not helpful.  
> **username_2**: @Ryan: Well, asking if it is harder than 3SAT does not make too much sense, theoretically speaking. This is supposed to be a high level TCS exchange site after all. If the comment will help clarify the question, why isn't it helpful? It was just a _comment_, intented to clarify the question, and not to give an answer.  
> **username_1**: @Moron: I think it is quite clear what is being asked.  
> **username_2**: @Ryan: I disagree. If it is possible the clarify the question exactly, why not? Perhaps it will also help clarify any confusion that might exist in Paul's mind.  
> **username_0**: @Ryan, @Moron: The intervals and the number of dimensions are *finite but large*. I am uncertain if the ability to have the less-than operator weakens the situation from the 'hardness' of N-SAT.  
> **username_1**: @Paul: thanks, I have lightly edited your question to reflect this.  
> **username_3**: It is difficult to distinguish between “bounded and reasonably small” and “bounded but can be very large” in complexity theory.  A usual way to cope with this is to pretend the latter to be unbounded.  
> **username_1**: @Paul: Note you can also prove hardness with $=$, not just $\geq$. Instead of $x_1 + x_2 + x_3 \geq 0$, use $(1-x_1)*(1-x_2)*(1-x_3)=0$.  
> **username_4**: @Paul: The list of operands you can use inside a predicate does not include "and", but you're using the comma as if it were an "and".  Should we consider "and" to be allowable in the definition of a predicate?  
> **username_0**: @Kurt: My bad. Yes. Commas in Prolog are indeed `and`.  

---

## 1 answers

### Answer by username_1 on 2010-09-10. Score: 7

And one way of trying to solve such a problem is to do a form of backtracking, or what is also called "branch-and-bound". (Sorry, this was too long for a comment.)

Here's one possible heuristic:

(1) Choose some variable $x$ that is "most" constrained in some sense (maybe it occurs the most often). Suppose its integer range is $[L,R]$, and let $M$ be the midpoint of that interval. Now try to recursively solve the problem when $x < M$ is assumed, and separately when $x \geq M$.

(2) In each recursive call, relax the predicate to be a linear program (i.e., the solutions to the variables are over the rationals), and include all range constraints such as $x \geq L$ and $x \leq R$. Check if the resulting linear program is still feasible over the rationals. If it isn't feasible over the rationals, then it won't be feasible over the integers either, so you can stop and backtrack. If it is feasible over the rationals, continue with step (1).

Note: not all possible constraints (e.g. quadratic polynomials like $x(1-x) = 0$) can be neatly expressed as linear constraints; one possible "solution" to this is to simply leave those constraints out (or, replace these "hard" constraints with linear constraints that are consequences of the hard constraint being true... for example, $x(1-x)=0$ has the consequence that $x \geq 0$ and $x \leq 1$).

That's about as much detail as a CS theory site can give you ;)

> **Comments:**
> **username_4**: But if this problem is NP-hard, then your heuristic isn't going to work so well for some instances, no? :)  It also seems that by relaxing the constraints with terms like x(1-x), you're getting rid of the very parts that make the problem interesting!  
> **username_1**: Of course it won't always work... that's why I called it a "heuristic" :) By the way, I think this kind of relaxation to linear programming is quite standard, but I don't remember where I first read about it.  
> **username_3**: To allow reader to find more about it, this method is called “branch-and-bound.”  
> **username_5**: I do not immediately see why the problem is reducible to 3sat (without a huge blowup to the given instance). The intervals the variables are contained inside might be very large. No?  
> **username_1**: If the interval endpoints are specified in binary along with the input, as well as the number of bits of precision (in unary), then the problem is in $NP$, and hence reducible to 3sat. If the precision is specified in binary then one runs into trouble.  

---

