Timeline for Is this problem mappable to 3SAT or is it weaker than 3SAT?
Current License: CC BY-SA 2.5
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 13, 2010 at 22:34 | history | edited | Paul Nathan | CC BY-SA 2.5 |
fixed operation list
|
| Sep 13, 2010 at 16:36 | comment | added | Paul Nathan |
@Kurt: My bad. Yes. Commas in Prolog are indeed and.
|
|
| Sep 11, 2010 at 3:30 | comment | added | Kurt | @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? | |
| Sep 10, 2010 at 21:02 | comment | added | Ryan Williams | @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$. | |
| Sep 10, 2010 at 20:44 | comment | added | Tsuyoshi Ito | 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. | |
| Sep 10, 2010 at 20:40 | comment | added | Ryan Williams | @Paul: thanks, I have lightly edited your question to reflect this. | |
| Sep 10, 2010 at 20:39 | history | edited | Ryan Williams | CC BY-SA 2.5 |
added 55 characters in body; edited tags
|
| Sep 10, 2010 at 19:39 | comment | added | Paul Nathan | @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. | |
| Sep 10, 2010 at 19:07 | comment | added | Aryabhata | @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. | |
| Sep 10, 2010 at 18:58 | comment | added | Ryan Williams | @Moron: I think it is quite clear what is being asked. | |
| Sep 10, 2010 at 18:51 | comment | added | Aryabhata | @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. | |
| Sep 10, 2010 at 18:45 | comment | added | Ryan Williams | @Moron: I took "10,000" to mean "essentially unbounded". The reply "$2^{10,000}$ is constant" is not helpful. | |
| Sep 10, 2010 at 18:36 | comment | added | Aryabhata | @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 :-) | |
| Sep 10, 2010 at 18:34 | comment | added | Ryan Williams | @Moron, the number of all possible satisfying assignments to a Boolean formula is also bounded above by a constant, $2^n$... | |
| Sep 10, 2010 at 18:31 | answer | added | Ryan Williams | timeline score: 7 | |
| Sep 10, 2010 at 18:26 | comment | added | Aryabhata | 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. | |
| Sep 10, 2010 at 18:22 | comment | added | Ryan Williams | 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. | |
| Sep 10, 2010 at 18:11 | history | asked | Paul Nathan | CC BY-SA 2.5 |