<p>Note: This is not really answering the question, this is just some comments posted as an answer. :)</p>
<p>Note that in VO, one is defining sets over the set of natural numbers (similar to sets defined in recursion theory) where as in descriptive complexity setting (SO, <span class="math-container">$\exists$</span>-SO, SO-Horn) we are talking about finite structures. An SO formula in the former setting will give not <span class="math-container">$PH$</span> but the whole analytical hierarchy as Arthur Milchior has written in his answer. IMHO, a better comparison would be with bounded arithmetic theories. I don't think you can get below c.e. sets unless you bound all quantifiers to finite domains, to get <span class="math-container">$P$</span> or <span class="math-container">$NP$</span> the size of domains should be very small.</p>
<blockquote>
<p>is the presence of one unbounded quantifier enough to capture c.e. sets?</p>
</blockquote>
<p>The problem is you probably want the language to be without extra symbols like equality, addition, multiplication (right?), if we had them then by MRDP theorem, Diophantine formulas (first-order existential quantifiers in front of an equality of two polynomials) would capture c.e. sets. If we are not allowing these symbols in the language, the problem is more complicated, one can use higher order quantifiers to define them, but that would increase the quantifier complexity. So if I want to give a short answer to your question about a single quantifier, I don't know.</p>
<p>If we can express <span class="math-container">$AC^0$</span>  relations in the language, then a single unbounded existential quantifier would suffice for capturing c.e. sets, the reason is <span class="math-container">$AC^0$</span> can check that a string <span class="math-container">$c$</span> is the computation of a TM <span class="math-container">$e$</span> on input <span class="math-container">$x$</span>. First-order formulas bounded by polynomials in presence of equality, addition, and multiplication capture PH, so if we have them in the language the answer is positive, but as I said you are probably looking for a language without these symbols.</p>
<h3>Some additional comments:</h3>
<p>Assume that we have a restriction of VO which can express at least <span class="math-container">$AC^0$</span>. Then a single unbounded existential quantifier of number type in front of those restricted formulas will give the whole c.e. sets.</p>

CC BY-SA 2.5
2010-10-04T00:46:03.853Z
2010-10-04T00:46:03.853Z
2020-06-17T09:38:08.363Z
Kaveh
<p>For information, VO is in fact really more powerful than what you state; it contains the entire analytical hierarchy (hence, also the entire arithmetical hierarchy). The result is not published, neither submitted to any place, but you can find it on my page, www.milchior.fr/ho.pdf section 7 page 47. </p>

<p>In it I show how VO lets you express addition and multiplication on order variable; may be some idea in this paper can help you. In particular I gave an equivalent definition (I prove it is equivalent) and I think it is more easy to use. (I wanted to avoid the fact that, in their definition of VO $\forall i \forall X^i\forall j\exists Y^j (X^i=Y^j)$ is false while    $\forall i \forall X^i\forall i\exists Y^i (X^i=Y^i)$ is true; which means that $i$ was changed after $X$ was quantified; hence it is useless to add "$^i$" when one quantifies $X$.</p>

<p>One straightforward restriction would be to forbid to quantify the same variable twice. I am pretty sure that the restriction is the class ELEMENTARY. The idea is that, for every formula $\phi(i)$ with a free order variable $i$, there would be one number $k$ such that forall $i>k$ the value of $\phi(i)$ would not change; hence if we can find this $k$ (which is probably an elementary function of the size of the universe) we can avoid to really check every possible $\phi(i)$ when we want the value of $\forall i \phi(i)$ but restrict it to $\forall i &lt; k \phi(i)$.</p>

<p>Else, you can certainly restrain VO by restraining the maximal order accepted; but then you obtain a "higher order" language (HO), and this is probably not what you want.</p>

CC BY-SA 2.5
2010-10-03T22:14:29.140Z
Thanks for the discussion, I will look at your reformulation.  Do you have any suggestions for some ways to restrict the logic so it isn't so powerful -- would something like requiring the unquantified part of the formula to be in CNF with Horn clauses likely to be useful, as it is with classical quantifiers?
András Salamon
CC BY-SA 2.5
2010-10-04T00:30:51.753Z
To be more precise, I mean a syntactic restriction along the lines of SNP, where the SO quantifiers are applied to a FO formula of specific form (for SNP, with universal FO quantifiers only), and then further restrictions are applied, such as the FO formula inside the FO quantifiers being Horn or Krom.  The last paragraph of your Section 5.3 talks about this, but I don't understand your comment that the approach is problematic.
András Salamon
CC BY-SA 2.5
2010-10-04T00:37:40.397Z
I  suggest that you read section 5.3 page 34 of my paper about the problem I met on Horn and Krom in High Order logic. You will meet the same problem in Variable Order (which is clearly a superset of High Order)
Arthur MILCHIOR
CC BY-SA 2.5
2010-10-03T21:55:10.683Z
2010-10-04T02:29:42.150Z
2010-10-04T02:29:42.150Z
Arthur MILCHIOR
<p>To answer to your comment, I guess I should make another answer, speaking only on Krom and Horn (May be I should ask a question about those to CSTheory)</p>

<p>I suggest that you read section 5.3 page 34 of my paper about the problem I met on Horn and Krom in High Order logic. You will meet the same problem in Variable Order (which is clearly a superset of High Order). </p>

<p>I don't know if you did pay attention to it, but SO(krom) is equal to P when the first order is universal; indeed you can express NP-complete problem if you add existantial first order variable. (I don't remember the example I had before, I can try to search it if you want it)</p>

<p>I don't know what this syntactical resctriction would become for high order or variable order logic... my point is just that you should also think of a good way to restrain quantifiers, because restraining the quantifier-free part alone is not usefull (at least for Krom formulae)</p>

CC BY-SA 2.5
2010-10-04T11:08:30.097Z
Thanks for the insight.  This definitely requires further thought!
András Salamon
CC BY-SA 2.5
2010-10-04T01:01:56.610Z
2010-10-04T01:01:56.610Z
Arthur MILCHIOR
<p>The paper</p>

<ul>
<li>Lauri Hella and José María Turull-Torres,
<em>Computing queries with higher-order logics</em>,
TCS <strong>355</strong> 197–214,
2006.
doi: <a href="http://dx.doi.org/doi:10.1016/j.tcs.2006.01.009">10.1016/j.tcs.2006.01.009</a></li>
</ul>

<p>proposes logic VO, variable-order logic.  This allows quantification over orders over the variables.  VO is quite powerful and can express some non-computable queries.  <em>(As pointed out by Arthur Milchior below, it actually captures the whole of the <a href="http://en.wikipedia.org/wiki/Analytical_hierarchy">analytical hierarchy</a>.)</em>  The authors show that the fragment of VO obtained by allowing only bounded universal quantification over the order variables exactly expresses all c.e. queries.  VO allows the order variables to range over the natural numbers, so bounding the order variables is clearly a natural condition to impose.</p>

<blockquote>
  <p>Is there a (nice) fragment of VO that captures P or NP?</p>
</blockquote>

<p>As an analogy, in classical first-order logic allowing quantification over sets of objects gives a more powerful logic called <a href="http://en.wikipedia.org/wiki/Second-order_logic">second-order logic</a> or SO.  SO captures the whole of the <a href="http://en.wikipedia.org/wiki/Polynomial_hierarchy">polynomial hierarchy</a>; this is usually written as PH = SO.  There are restricted forms of SO capturing important complexity classes: NP = $\exists$SO, P = SO-Horn, and NL = SO-Krom.  These are obtained by imposing restrictions on the syntax of allowed formulas.</p>

<p>So there are straightforward ways to restrict SO to obtain interesting classes.  I would like to know if there are similar straightforward restrictions of VO that are roughly the right level of expressivity for P or NP.  If such restrictions are not known I would be interested in suggestions for likely candidates, or in some arguments why such restrictions are unlikely to exist.</p>

<p>I have checked the (few) papers that cite this one, and checked the obvious phrases on Google and Scholar, but found nothing obviously relevant.  Most of the papers dealing with logics more powerful than first-order don't seem to deal with restrictions to bring down the power into the realm of "reasonable" computations, but seem content to dwell in the c.e. universe of arithmetic and analytic classes.  I'd be happy with a pointer or a non-obvious phrase to search on; this might be well known to someone working in higher-order logics.</p>

CC BY-SA 2.5
2010-10-03T18:59:09.297Z
While the abbreviations are famous among the CS community, I'd like to expand them for "the rest of us": PH (Polynomial-time Hierarchy), SO (Second-Order logic), and VO (Variable-Order logic).
Sadeq Dousti
CC BY-SA 2.5
2010-10-03T19:38:16.307Z
In fact I've never heard of VO before this, so thanks for the clarification.
Suresh Venkat
CC BY-SA 2.5
2010-10-03T19:52:17.673Z
@Suresh: Yes, I forgot to say that VO is not well-known at all. Anyway, you are most welcome!
Sadeq Dousti
CC BY-SA 2.5
2010-10-03T19:57:59.197Z
There's a nice illustration of various logics and complexity classes here: http://www.cs.umass.edu/~immerman/descriptive_complexity.html, though it does not mention VO.
Sadeq Dousti
CC BY-SA 2.5
2010-10-03T21:18:11.287Z
Perhaps I wasn't clear: VO was defined less than a decade ago, and is not well-known. I am interested in it because it is a way to extend first-order logic to make it more powerful, without using fixed-point operators.
András Salamon
CC BY-SA 2.5
2010-10-04T00:16:06.140Z
Note that in VO, one is defining sets over the set of natural numbers (similar to sets defined in recursion theory) where as in descriptive complexity setting (SO, $\exists$-SO, SO-Horn) we are talking about finite structures. An SO formula in the former setting will give not $PH$ but the whole analytical hierarchy as Arthur Milchior has written in his answer. IMHO, a better comparison would be with bounded arithmetic theories. I don't think you can get below c.e. sets unless you bound all quantifiers to finite domains, to get $P$ or $NP$ the size of domains should be very small.
Kaveh
CC BY-SA 2.5
2010-10-04T00:21:09.340Z
@Kaveh: some kind of bounded quantifiers sounds promising.  I'd be happy to severely restrict the logic as long as the resulting fragment has reasonable complexity.  It might also be interesting to see if your statement can be made precise: is the presence of one unbounded quantifier enough to capture c.e. sets?
András Salamon
CC BY-SA 2.5
2010-10-04T00:36:08.260Z
@Kaveh: It might be worth turning your thoughts into an answer!
András Salamon
<cc.complexity-theory><complexity-classes><lo.logic><computability><descriptive-complexity>
Is there a natural restriction of VO logic which captures P or NP?
András Salamon
# Is there a natural restriction of VO logic which captures P or NP?

(Asked by: username_0 on 2010-10-03)

The paper

* Lauri Hella and José María Turull-Torres,
  *Computing queries with higher-order logics*,
  TCS **355** 197–214,
  2006.
  doi: [10.1016/j.tcs.2006.01.009](http://dx.doi.org/doi:10.1016/j.tcs.2006.01.009)

proposes logic VO, variable-order logic. This allows quantification over orders over the variables. VO is quite powerful and can express some non-computable queries. *(As pointed out by Arthur Milchior below, it actually captures the whole of the [analytical hierarchy](http://en.wikipedia.org/wiki/Analytical_hierarchy).)* The authors show that the fragment of VO obtained by allowing only bounded universal quantification over the order variables exactly expresses all c.e. queries. VO allows the order variables to range over the natural numbers, so bounding the order variables is clearly a natural condition to impose.

> Is there a (nice) fragment of VO that captures P or NP?

As an analogy, in classical first-order logic allowing quantification over sets of objects gives a more powerful logic called [second-order logic](http://en.wikipedia.org/wiki/Second-order_logic) or SO. SO captures the whole of the [polynomial hierarchy](http://en.wikipedia.org/wiki/Polynomial_hierarchy); this is usually written as PH = SO. There are restricted forms of SO capturing important complexity classes: NP = $\exists$SO, P = SO-Horn, and NL = SO-Krom. These are obtained by imposing restrictions on the syntax of allowed formulas.

So there are straightforward ways to restrict SO to obtain interesting classes. I would like to know if there are similar straightforward restrictions of VO that are roughly the right level of expressivity for P or NP. If such restrictions are not known I would be interested in suggestions for likely candidates, or in some arguments why such restrictions are unlikely to exist.

I have checked the (few) papers that cite this one, and checked the obvious phrases on Google and Scholar, but found nothing obviously relevant. Most of the papers dealing with logics more powerful than first-order don't seem to deal with restrictions to bring down the power into the realm of "reasonable" computations, but seem content to dwell in the c.e. universe of arithmetic and analytic classes. I'd be happy with a pointer or a non-obvious phrase to search on; this might be well known to someone working in higher-order logics.

**Tags:** cc.complexity-theory, complexity-classes, lo.logic, computability, descriptive-complexity
> **Comments:**
> **username_1**: While the abbreviations are famous among the CS community, I'd like to expand them for "the rest of us": PH (Polynomial-time Hierarchy), SO (Second-Order logic), and VO (Variable-Order logic).  
> **username_2**: In fact I've never heard of VO before this, so thanks for the clarification.  
> **username_1**: @Suresh: Yes, I forgot to say that VO is not well-known at all. Anyway, you are most welcome!  
> **username_1**: There's a nice illustration of various logics and complexity classes here: http://www.cs.umass.edu/~immerman/descriptive_complexity.html, though it does not mention VO.  
> **username_0**: Perhaps I wasn't clear: VO was defined less than a decade ago, and is not well-known. I am interested in it because it is a way to extend first-order logic to make it more powerful, without using fixed-point operators.  
> **username_3**: Note that in VO, one is defining sets over the set of natural numbers (similar to sets defined in recursion theory) where as in descriptive complexity setting (SO, $\exists$-SO, SO-Horn) we are talking about finite structures. An SO formula in the former setting will give not $PH$ but the whole analytical hierarchy as Arthur Milchior has written in his answer. IMHO, a better comparison would be with bounded arithmetic theories. I don't think you can get below c.e. sets unless you bound all quantifiers to finite domains, to get $P$ or $NP$ the size of domains should be very small.  
> **username_0**: @Kaveh: some kind of bounded quantifiers sounds promising.  I'd be happy to severely restrict the logic as long as the resulting fragment has reasonable complexity.  It might also be interesting to see if your statement can be made precise: is the presence of one unbounded quantifier enough to capture c.e. sets?  
> **username_0**: @Kaveh: It might be worth turning your thoughts into an answer!  

---

## 3 answers

### Answer by username_3 on 2010-10-04. Score: 4 | Accepted answer

Note: This is not really answering the question, this is just some comments posted as an answer. :)

Note that in VO, one is defining sets over the set of natural numbers (similar to sets defined in recursion theory) where as in descriptive complexity setting (SO, $\exists$-SO, SO-Horn) we are talking about finite structures. An SO formula in the former setting will give not $PH$ but the whole analytical hierarchy as Arthur Milchior has written in his answer. IMHO, a better comparison would be with bounded arithmetic theories. I don't think you can get below c.e. sets unless you bound all quantifiers to finite domains, to get $P$ or $NP$ the size of domains should be very small.

> is the presence of one unbounded quantifier enough to capture c.e. sets?

The problem is you probably want the language to be without extra symbols like equality, addition, multiplication (right?), if we had them then by MRDP theorem, Diophantine formulas (first-order existential quantifiers in front of an equality of two polynomials) would capture c.e. sets. If we are not allowing these symbols in the language, the problem is more complicated, one can use higher order quantifiers to define them, but that would increase the quantifier complexity. So if I want to give a short answer to your question about a single quantifier, I don't know.

If we can express $AC^0$ relations in the language, then a single unbounded existential quantifier would suffice for capturing c.e. sets, the reason is $AC^0$ can check that a string $c$ is the computation of a TM $e$ on input $x$. First-order formulas bounded by polynomials in presence of equality, addition, and multiplication capture PH, so if we have them in the language the answer is positive, but as I said you are probably looking for a language without these symbols.

### Some additional comments:

Assume that we have a restriction of VO which can express at least $AC^0$. Then a single unbounded existential quantifier of number type in front of those restricted formulas will give the whole c.e. sets.


---

### Answer by username_4 on 2010-10-03. Score: 4

For information, VO is in fact really more powerful than what you state; it contains the entire analytical hierarchy (hence, also the entire arithmetical hierarchy). The result is not published, neither submitted to any place, but you can find it on my page, www.milchior.fr/ho.pdf section 7 page 47.

In it I show how VO lets you express addition and multiplication on order variable; may be some idea in this paper can help you. In particular I gave an equivalent definition (I prove it is equivalent) and I think it is more easy to use. (I wanted to avoid the fact that, in their definition of VO $\forall i \forall X^i\forall j\exists Y^j (X^i=Y^j)$ is false while $\forall i \forall X^i\forall i\exists Y^i (X^i=Y^i)$ is true; which means that $i$ was changed after $X$ was quantified; hence it is useless to add "$^i$" when one quantifies $X$.

One straightforward restriction would be to forbid to quantify the same variable twice. I am pretty sure that the restriction is the class ELEMENTARY. The idea is that, for every formula $\phi(i)$ with a free order variable $i$, there would be one number $k$ such that forall $i>k$ the value of $\phi(i)$ would not change; hence if we can find this $k$ (which is probably an elementary function of the size of the universe) we can avoid to really check every possible $\phi(i)$ when we want the value of $\forall i \phi(i)$ but restrict it to $\forall i < k \phi(i)$.

Else, you can certainly restrain VO by restraining the maximal order accepted; but then you obtain a "higher order" language (HO), and this is probably not what you want.

> **Comments:**
> **username_0**: Thanks for the discussion, I will look at your reformulation.  Do you have any suggestions for some ways to restrict the logic so it isn't so powerful -- would something like requiring the unquantified part of the formula to be in CNF with Horn clauses likely to be useful, as it is with classical quantifiers?  
> **username_0**: To be more precise, I mean a syntactic restriction along the lines of SNP, where the SO quantifiers are applied to a FO formula of specific form (for SNP, with universal FO quantifiers only), and then further restrictions are applied, such as the FO formula inside the FO quantifiers being Horn or Krom.  The last paragraph of your Section 5.3 talks about this, but I don't understand your comment that the approach is problematic.  
> **username_4**: I  suggest that you read section 5.3 page 34 of my paper about the problem I met on Horn and Krom in High Order logic. You will meet the same problem in Variable Order (which is clearly a superset of High Order)  

---

### Answer by username_4 on 2010-10-04. Score: 2

To answer to your comment, I guess I should make another answer, speaking only on Krom and Horn (May be I should ask a question about those to CSTheory)

I suggest that you read section 5.3 page 34 of my paper about the problem I met on Horn and Krom in High Order logic. You will meet the same problem in Variable Order (which is clearly a superset of High Order).

I don't know if you did pay attention to it, but SO(krom) is equal to P when the first order is universal; indeed you can express NP-complete problem if you add existantial first order variable. (I don't remember the example I had before, I can try to search it if you want it)

I don't know what this syntactical resctriction would become for high order or variable order logic... my point is just that you should also think of a good way to restrain quantifiers, because restraining the quantifier-free part alone is not usefull (at least for Krom formulae)

> **Comments:**
> **username_0**: Thanks for the insight.  This definitely requires further thought!  

---

