<p>The definition of a logic&nbsp;$\mathcal{L}$ capturing a complexity class&nbsp;$\mathcal{C}$ requires that the problem of evaluating $\mathcal{L}$-formulas is itself in&nbsp;$\mathcal{C}$.  However, evaluating formulas of the logic you suggest is <strong>coNP</strong>-complete (in fact, even without the fixed points).</p>

<ul>
<li><p><strong>Membership</strong>. You can determine that $\mathfrak{A}\nvDash^* \varphi$ by guessing a linear order and checking that it makes the formula false.</p></li>
<li><p><strong>Completeness</strong>. A graph is non-3-colourable if, and only if, every linear order $\leq$ on its vertices satisfies the property that, for every pair $x$, $y$ of vertices, at least one of the the vertex sets $\{z\mid z&lt;x\}$, $\{z\mid x\leq z&lt;y\}$ and $\{z\mid y\leq z\}$ contains an edge.  This property is definable without using the fixed point operator.</p></li>
</ul>

<p>You could try to get around this by defining the formulas of the logic to be only the order-invariant $\mathrm{IFP}(\tau+&lt;)$ formulas, i.e., those that are true for some linear order if, and only if, they are true for all. But it's an easy consequence of Trakhtenbrot's theorem that this class of formulas is undecidable.</p>

CC BY-SA 3.0
2013-11-25T16:29:32.377Z
2013-11-25T16:29:32.377Z
David Richerby
<p>This semantic is powerful enough to embed co-$NP$-complete problems. For instance, on an input graph $G$, you can design $\phi$ to say "the even elements according to $&lt;$ do not form a clique".</p>

<p>Then, under your semantic, $G\models^* \phi$ iff $G$ does not have a clique which is half the size of $G$. It is not hard to verify that this is a co-$NP$-complete problem, so unless $P=NP$, your logic is more powerful than $P$.</p>

CC BY-SA 3.0
2013-11-25T16:27:12.333Z
2013-11-25T16:32:20.627Z
2013-11-25T16:32:20.627Z
Denis
<p>Consider the logic whose $\tau$-sentences are the sentences in $IFP(\tau \cup \{&lt;\})$, and the satisfaction relation is given by $\mathfrak{A} \models^* \phi$ if $(\mathfrak{A}, &lt;)  \models \phi$ for every ordering $&lt;$ of $\mathfrak{A}$. Why does this logic not capture PTIME? I suppose that it is because a machine cannot quickly determine whether whether all linear orderings satisfy the sentence, but is there a formal proof of this?</p>

<cc.complexity-theory><lo.logic>
Why does IFP< not capture PTIME?
CS-Curious
# Why does IFP< not capture PTIME?

(Asked by: username_0 on 2013-11-25)

Consider the logic whose $\tau$-sentences are the sentences in $IFP(\tau \cup \{<\})$, and the satisfaction relation is given by $\mathfrak{A} \models^\* \phi$ if $(\mathfrak{A}, <) \models \phi$ for every ordering $<$ of $\mathfrak{A}$. Why does this logic not capture PTIME? I suppose that it is because a machine cannot quickly determine whether whether all linear orderings satisfy the sentence, but is there a formal proof of this?

**Tags:** cc.complexity-theory, lo.logic


---

## 2 answers

### Answer by username_1 on 2013-11-25. Score: 4

The definition of a logic $\mathcal{L}$ capturing a complexity class $\mathcal{C}$ requires that the problem of evaluating $\mathcal{L}$-formulas is itself in $\mathcal{C}$. However, evaluating formulas of the logic you suggest is **coNP**-complete (in fact, even without the fixed points).

* **Membership**. You can determine that $\mathfrak{A}\nvDash^\* \varphi$ by guessing a linear order and checking that it makes the formula false.
* **Completeness**. A graph is non-3-colourable if, and only if, every linear order $\leq$ on its vertices satisfies the property that, for every pair $x$, $y$ of vertices, at least one of the the vertex sets $\{z\mid z

You could try to get around this by defining the formulas of the logic to be only the order-invariant $\mathrm{IFP}(\tau+<)$ formulas, i.e., those that are true for some linear order if, and only if, they are true for all. But it's an easy consequence of Trakhtenbrot's theorem that this class of formulas is undecidable.


---

### Answer by username_2 on 2013-11-25. Score: 2

This semantic is powerful enough to embed co-$NP$-complete problems. For instance, on an input graph $G$, you can design $\phi$ to say "the even elements according to $<$ do not form a clique".

Then, under your semantic, $G\models^\* \phi$ iff $G$ does not have a clique which is half the size of $G$. It is not hard to verify that this is a co-$NP$-complete problem, so unless $P=NP$, your logic is more powerful than $P$.


---

