<p>I have found <a href="http://www.openproblemgarden.org/op/monadic_second_order_logic_with_cardinality_predicates" rel="noreferrer">the following question</a> at openproblemgarden.org:</p>

<p>The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:</p>

<ul>
<li><p><span class="math-container">$\text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''} $</span></p></li>
<li><p><span class="math-container">$ \text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{''} $</span> </p></li>
</ul>

<p>where <span class="math-container">$ A $</span> is a fixed recursive set of integers.</p>

<p>Let us fix <span class="math-container">$ k $</span> and a closed formula <span class="math-container">$ F $</span> in this language.</p>

<p><strong>Conjecture</strong>   Is it true that the validity of <span class="math-container">$ F $</span> for a graph <span class="math-container">$ G $</span> of tree-width at most <span class="math-container">$ k $</span> can be tested in polynomial time in the size of <span class="math-container">$ G $</span>?</p>

<hr>

<p>I think that this conjecture of course false:</p>

<p>Consider some set <span class="math-container">$A$</span> such that <span class="math-container">$A$</span> recursive but <span class="math-container">$A$</span> is <strong>EEXP</strong>-hard.<br>
Consider the formula <span class="math-container">$ \text{``}\,\mathrm{Card}(V) \text{ belongs to } A\,\text{''} $</span>, where <span class="math-container">$V$</span> is the set of vertices.</p>

<p>Now assume that the conjecture is true. I claim that in this case <span class="math-container">$A$</span> belongs to  <strong>EXP</strong> that contradict to Time-hierarchy theorem. Consider the following algorithm deciding <span class="math-container">$A$</span>:</p>

<p>On input <span class="math-container">$n$</span> construct a tree with <span class="math-container">$n$</span> vertices. By the conjecture we can decides does <span class="math-container">$n$</span> belongs to <span class="math-container">$A$</span> in time <span class="math-container">$\text{poly}(n)$</span> that is <span class="math-container">$2^{\text{poly}(\text{the size of the input})}$</span>.</p>

<p>Am I wrong?</p>

CC BY-SA 4.0
2019-10-09T14:20:11.437Z
This may well be a mistake in the Open Problem Garden. Unfortunately, they do not give a reference to the original.
Emil Jeřábek
CC BY-SA 4.0
2019-10-09T15:25:22.900Z
The author of the Open Problem Garden question (dberwanger) should be Dietmar Berwanger from CNRS; http://www.lsv.fr/~dwb/ . You could contact him by email.
Gamow
CC BY-SA 4.0
2019-10-09T17:04:58.530Z
I believe that the autor meant the version of the problem where have an oracle in A, i.e., you can check whether card(V) belongs to A in a single step.
Bartosz Bednarczyk
CC BY-SA 4.0
2019-10-10T09:43:56.227Z
I tried to post a comment at the OPG page.
Emil Jeřábek
CC BY-SA 4.0
2019-10-10T11:14:30.503Z
@EmilJeřábek Dietmar Berwanger  wrote me that he agrees with the solution (However it is Courcelle's question he just put it at the cite.) It seems that nobody really thought about it)).
Alexey Milovanov
CC BY-SA 4.0
2019-10-10T11:15:43.060Z
There is another question: what if add only formulas ``Card()=Card()''? I think I can prove that the problem will be NP-hard by reduction of 3-Partition.
Alexey Milovanov
CC BY-SA 4.0
2019-10-10T12:26:56.487Z
Might be interesting: https://arxiv.org/abs/1703.00544
Bartosz Bednarczyk
<cc.complexity-theory><complexity-classes><lo.logic><polynomial-time>
On Courcelle's question about Monadic second-order logic with cardinality predicates
Alexey Milovanov
# On Courcelle's question about Monadic second-order logic with cardinality predicates

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

I have found [the following question](http://www.openproblemgarden.org/op/monadic_second_order_logic_with_cardinality_predicates) at openproblemgarden.org:

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:

* $\text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''} $
* $ \text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{''} $

where $ A $ is a fixed recursive set of integers.

Let us fix $ k $ and a closed formula $ F $ in this language.

**Conjecture** Is it true that the validity of $ F $ for a graph $ G $ of tree-width at most $ k $ can be tested in polynomial time in the size of $ G $?

---

I think that this conjecture of course false:

Consider some set $A$ such that $A$ recursive but $A$ is **EEXP**-hard.  
Consider the formula $ \text{``}\,\mathrm{Card}(V) \text{ belongs to } A\,\text{''} $, where $V$ is the set of vertices.

Now assume that the conjecture is true. I claim that in this case $A$ belongs to **EXP** that contradict to Time-hierarchy theorem. Consider the following algorithm deciding $A$:

On input $n$ construct a tree with $n$ vertices. By the conjecture we can decides does $n$ belongs to $A$ in time $\text{poly}(n)$ that is $2^{\text{poly}(\text{the size of the input})}$.

Am I wrong?

**Tags:** cc.complexity-theory, complexity-classes, lo.logic, polynomial-time
> **Comments:**
> **username_1**: This may well be a mistake in the Open Problem Garden. Unfortunately, they do not give a reference to the original.  
> **username_2**: The author of the Open Problem Garden question (dberwanger) should be Dietmar Berwanger from CNRS; http://www.lsv.fr/~dwb/ . You could contact him by email.  
> **username_3**: I believe that the autor meant the version of the problem where have an oracle in A, i.e., you can check whether card(V) belongs to A in a single step.  
> **username_1**: I tried to post a comment at the OPG page.  
> **username_0**: @EmilJeřábek Dietmar Berwanger  wrote me that he agrees with the solution (However it is Courcelle's question he just put it at the cite.) It seems that nobody really thought about it)).  
> **username_0**: There is another question: what if add only formulas ``Card()=Card()''? I think I can prove that the problem will be NP-hard by reduction of 3-Partition.  
> **username_3**: Might be interesting: https://arxiv.org/abs/1703.00544  

---

## 0 answers

