I have found the following question 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?

  • 3
    $\begingroup$ This may well be a mistake in the Open Problem Garden. Unfortunately, they do not give a reference to the original. $\endgroup$ Oct 9, 2019 at 14:20
  • 3
    $\begingroup$ The author of the Open Problem Garden question (dberwanger) should be Dietmar Berwanger from CNRS; lsv.fr/~dwb . You could contact him by email. $\endgroup$
    – Gamow
    Oct 9, 2019 at 15:25
  • $\begingroup$ 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. $\endgroup$ Oct 9, 2019 at 17:04
  • 1
    $\begingroup$ I tried to post a comment at the OPG page. $\endgroup$ Oct 10, 2019 at 9:43
  • 2
    $\begingroup$ Might be interesting: arxiv.org/abs/1703.00544 $\endgroup$ Oct 10, 2019 at 12:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.