Timeline for Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 19 at 16:39 | comment | added | Peter Taylor | @BrendanMcKay, if this kind of approach does meet OP's goals then I think having the variables be quadratic in the number of vertices might actually be better than linear, because there are $2^{O(n^2)}$ possible edge sets. | |
| Mar 19 at 5:24 | comment | added | Brendan McKay | Similarly to Peter's comment, the NP-hard problem of 3-edge-colouring a cubic graph needs a number of variables and clauses both linear in the size of the graph. | |
| Mar 18 at 20:18 | comment | added | Peter Taylor | I haven't worked through the details, but I think that TSP on $n$ vertices can be reduced to 3SAT with $O(n^2)$ variables and $O(n^2)$ clauses. What I'm not sure is whether that addresses your question. Would "the set of problems produced by X reduction from a different NP-complete problem" be an acceptable answer in principle, if the details work out? | |
| Mar 18 at 16:32 | history | edited | Logan | CC BY-SA 4.0 |
added 5 characters in body
|
| Mar 18 at 16:24 | history | edited | Logan | CC BY-SA 4.0 |
added 267 characters in body
|
| Mar 18 at 15:52 | history | edited | Logan | CC BY-SA 4.0 |
added 217 characters in body
|
| Mar 18 at 14:11 | history | edited | Logan | CC BY-SA 4.0 |
added 642 characters in body
|
| Mar 18 at 13:48 | history | edited | gmvh | CC BY-SA 4.0 |
MathJaxed title, added tags
|
| Mar 18 at 12:42 | comment | added | Daniel Weber | I'm not convinced by your intuition — while each hard instance might only have $O(n)$ clauses, in total there are still $\binom{\binom{n}3}n = O(n^2)^n = 2^{2n\log n+o(n \log n)}$ problems, which is still quite a lot. It might be more reasonable to ask for that, though | |
| Mar 18 at 7:49 | history | edited | YCor | CC BY-SA 4.0 |
edited tags, formatting
|
| Mar 18 at 5:39 | comment | added | Logan | I calculated the number of linear SAT problems for n=1...5 n = 1: 3 n = 2: 143 n = 3: 16705 n = 4: 3382629 n = 5: 1061378399 It's certainly slower than 3-SAT but still looks faster than $2^{c n}$ | |
| Mar 18 at 3:51 | history | edited | Logan | CC BY-SA 4.0 |
added 4 characters in body
|
| Mar 18 at 3:51 | comment | added | Logan | yeah, I meant 2**(8*choose(n,3)), editing | |
| Mar 17 at 21:36 | comment | added | Joel David Hamkins | You say that the number of 3-SAT problems is $8({n\atop 3})$, but I would describe this as the number of 3-SAT clauses. A 3-SAT problem, after all (and which clearly you know), is a finite list of such clauses. | |
| Mar 17 at 20:12 | comment | added | Steven Stadnicki | You might want to have a look at Linear SAT: sciencedirect.com/science/article/pii/S0166218X18302695 — I think (though I have not done the math) that these constraints should lead to an exponential number of clauses. | |
| Mar 17 at 19:54 | comment | added | Geoffrey Irving | Yes, but for boring padding reasons: it suffices to ignore all but $\sqrt{n}$ of the variables. But if you somehow rule out padding, my guess is that the new version would be open, as it feels close to an NP-complete average-case hard problem. | |
| S Mar 17 at 19:21 | review | First questions | |||
| Mar 17 at 21:29 | |||||
| S Mar 17 at 19:21 | history | asked | Logan | CC BY-SA 4.0 |