<p>In <a href="https://cstheory.stackexchange.com/questions/30881">this question</a> and its answer, they discuss about reducing CNF-SAT with <span class="math-container">$n$</span> variables and <span class="math-container">$m$</span> clauses to a (problem on) planar graph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$|V|$</span> as small as possible. It is said that the best known reduction has <span class="math-container">$|V| = m^2$</span>, and that if a better reduction with <span class="math-container">$|V| \in o(m^2)$</span> is found, that would refute ETH.</p>
<hr />
<p>There is a reduction from <span class="math-container">$\oplus k$</span>-SAT with <span class="math-container">$n$</span> variables and <span class="math-container">$m$</span> clauses to <span class="math-container">$\oplus$</span>VERTEX COVER where the output graph <span class="math-container">$G=(V,E)$</span> is planar and has <span class="math-container">$|V| = 51(k+1)nm$</span>. Such reduction clearly meets the <span class="math-container">$|V| \in o(m^2)$</span> requirement when <span class="math-container">$k$</span> is a constant and <span class="math-container">$m$</span> is superlinear in <span class="math-container">$n$</span>.</p>
<hr />
<blockquote>
<p><strong>Question</strong><br />
Can the same line of reasoning made within the linked question be applied here in order to refute <span class="math-container">$\oplus$</span>ETH, or am I missing some important detail?</p>
</blockquote>

CC BY-SA 4.0
2020-08-08T10:59:11.300Z
What is $\oplus$ETH?
Emil Jeřábek
CC BY-SA 4.0
2020-08-08T12:12:09.310Z
@EmilJeřábek: In the paper https://arxiv.org/pdf/1112.2275.pdf, $\oplus$SETH is mentioned. From page 3: "Formally, $\oplus$SETH asserts that, for all $\epsilon$ < 1,
there exists a (large) integer $k$ such that $\oplus k$-SAT cannot be computed in time $O(2^{\epsilon n})$". Unless I'm wrong, such definition is to $\oplus k$-SAT as the SETH is to $k$-SAT. Then, I've imagined that if $\oplus$SETH was introduced, then so was $\oplus$ETH... Is it the case that, while $\oplus$SETH exists as a conjecture, there is no such thing as $\oplus$ETH?
Giorgio Camerani
CC BY-SA 4.0
2020-08-08T13:19:58.113Z
I didn’t say that it didn’t exist. I simply asked what it was. “Exists” can mean anything between “someone mentioned it in passing in one obscure paper”, and “it is widely known in the field”.
Emil Jeřábek
CC BY-SA 4.0
2020-08-12T14:30:35.180Z
Why do you assume that $n = o(m)$? To my understanding, for the purposes of ETH (not sure about $\oplus ETH$) we should assume that $m = \Theta(n)$.
Laakeri
CC BY-SA 4.0
2020-08-13T11:06:55.163Z
@Laakeri: Maybe you're right, but then why in the linked question and its answer there is no such limitation? They pose no constraints on $m$. I imagine they implicitly refer to the Sparsification Lemma, but even in such case there is something unclear to me: suppose they take a CNF with unbounded $m$ and reduce it to a subexponential number of CNFs having $m' = \Theta(n)$, then they turn each of such CNFs into a planar graph to take profit of its sublinear treewidth. Even if this is their reasoning, why they write $|V| \in o(m^2)$, being $m$ the number of clauses of the original formula? ...
Giorgio Camerani
CC BY-SA 4.0
2020-08-13T11:21:55.273Z
@Laakeri: ... In order to claim the disproval of ETH they should have written $|V| \in o(n^2)$, no? In which case it wouldn't have been surprising and I wouldn't have raised this question. On the other hand, it might be that in the linked question they assume, since the very beginning, that the original formula already has $m = \Theta(n)$: but again, if that's the case, why writing $|V| \in o(m^2)$, and why using the $m$ variable at all rather than simply saying that the original formula had $cn$ clauses for some constant $c$?
Giorgio Camerani
CC BY-SA 4.0
2020-08-13T11:25:33.737Z
I do not understand why they use $m$ instead of $n$ in the linked question either... Probably they assume that $n < m$, which makes their argument correct, and is probably fair to assume. Assuming that $n = o(m)$ is much stronger than this.
Laakeri
CC BY-SA 4.0
2023-12-13T17:40:06.430Z
A disproval of $\oplus ETH$ would also be a disproval of ETH, because there is a randomized reduction from NP to UP.
rus9384
<cc.complexity-theory><graph-theory><sat><counting-complexity><planar-graphs>
Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?
Giorgio Camerani
# Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?

(Asked by: username_0 on 2020-08-08)

In [this question](https://cstheory.stackexchange.com/questions/30881) and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the best known reduction has $|V| = m^2$, and that if a better reduction with $|V| \in o(m^2)$ is found, that would refute ETH.

---

There is a reduction from $\oplus k$-SAT with $n$ variables and $m$ clauses to $\oplus$VERTEX COVER where the output graph $G=(V,E)$ is planar and has $|V| = 51(k+1)nm$. Such reduction clearly meets the $|V| \in o(m^2)$ requirement when $k$ is a constant and $m$ is superlinear in $n$.

---

> **Question**  
> Can the same line of reasoning made within the linked question be applied here in order to refute $\oplus$ETH, or am I missing some important detail?

**Tags:** cc.complexity-theory, graph-theory, sat, counting-complexity, planar-graphs
> **Comments:**
> **username_1**: What is $\oplus$ETH?  
> **username_0**: @EmilJeřábek: In the paper https://arxiv.org/pdf/1112.2275.pdf, $\oplus$SETH is mentioned. From page 3: "Formally, $\oplus$SETH asserts that, for all $\epsilon$ < 1, there exists a (large) integer $k$ such that $\oplus k$-SAT cannot be computed in time $O(2^{\epsilon n})$". Unless I'm wrong, such definition is to $\oplus k$-SAT as the SETH is to $k$-SAT. Then, I've imagined that if $\oplus$SETH was introduced, then so was $\oplus$ETH... Is it the case that, while $\oplus$SETH exists as a conjecture, there is no such thing as $\oplus$ETH?  
> **username_1**: I didn’t say that it didn’t exist. I simply asked what it was. “Exists” can mean anything between “someone mentioned it in passing in one obscure paper”, and “it is widely known in the field”.  
> **username_2**: Why do you assume that $n = o(m)$? To my understanding, for the purposes of ETH (not sure about $\oplus ETH$) we should assume that $m = \Theta(n)$.  
> **username_0**: @Laakeri: Maybe you're right, but then why in the linked question and its answer there is no such limitation? They pose no constraints on $m$. I imagine they implicitly refer to the Sparsification Lemma, but even in such case there is something unclear to me: suppose they take a CNF with unbounded $m$ and reduce it to a subexponential number of CNFs having $m' = \Theta(n)$, then they turn each of such CNFs into a planar graph to take profit of its sublinear treewidth. Even if this is their reasoning, why they write $|V| \in o(m^2)$, being $m$ the number of clauses of the original formula? ...  
> **username_0**: @Laakeri: ... In order to claim the disproval of ETH they should have written $|V| \in o(n^2)$, no? In which case it wouldn't have been surprising and I wouldn't have raised this question. On the other hand, it might be that in the linked question they assume, since the very beginning, that the original formula already has $m = \Theta(n)$: but again, if that's the case, why writing $|V| \in o(m^2)$, and why using the $m$ variable at all rather than simply saying that the original formula had $cn$ clauses for some constant $c$?  
> **username_2**: I do not understand why they use $m$ instead of $n$ in the linked question either... Probably they assume that $n < m$, which makes their argument correct, and is probably fair to assume. Assuming that $n = o(m)$ is much stronger than this.  
> **username_3**: A disproval of $\oplus ETH$ would also be a disproval of ETH, because there is a randomized reduction from NP to UP.  

---

## 0 answers

