<p>I was going through Fagin's Theorem (summary on <a href="https://en.wikipedia.org/wiki/Fagin&#39;s_theorem" rel="nofollow noreferrer">wiki</a>) and if I understood correctly Existential Second Order Logic (ESO) can be used to represent any NP problem, the same can be said for a Non-deterministic Turing Machine. 
Now I have a few questions about that:</p>

<ol>
<li>If ESO logic is enough to characterise all the NP problems, what does the full Second Order Logic (SOL) characterise more?</li>
<li>If the answer to the first question is "nothing more", does that mean that any SOL can be reduced to ESO logic (it is true already that Higher Order Logics can be reduced to SOL for instance...)?</li>
<li>Perhaps I am missing and confusing something to have such questions in mind. Would it be possible to have some papers' link to fill in the gap?</li>
</ol>

CC BY-SA 4.0
2019-10-13T15:58:31.183Z
1. All of second order logic corresponds to the whole polynomial hierarchy.
2. Accordingly, your (2) is asking whether the polynomial hierarchy collapses to NP.
3. Take a look at Neil Immerman's summary of (https://people.cs.umass.edu/~immerman/descriptive_complexity.html) and book on (https://people.cs.umass.edu/~immerman/book/ch0_1_2.pdf) descriptive complexity.
Huck Bennett
CC BY-SA 4.0
2019-10-14T07:00:00.077Z
Thanks @HuckBennett that's helpful!
gifa
<lo.logic><np>
Fagin's Theorem implications
gifa
# Fagin's Theorem implications

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

I was going through Fagin's Theorem (summary on [wiki](https://en.wikipedia.org/wiki/Fagin's_theorem)) and if I understood correctly Existential Second Order Logic (ESO) can be used to represent any NP problem, the same can be said for a Non-deterministic Turing Machine.
Now I have a few questions about that:

1. If ESO logic is enough to characterise all the NP problems, what does the full Second Order Logic (SOL) characterise more?
2. If the answer to the first question is "nothing more", does that mean that any SOL can be reduced to ESO logic (it is true already that Higher Order Logics can be reduced to SOL for instance...)?
3. Perhaps I am missing and confusing something to have such questions in mind. Would it be possible to have some papers' link to fill in the gap?

**Tags:** lo.logic, np

> **Comments:**
> **username_1**: 1. All of second order logic corresponds to the whole polynomial hierarchy. 2. Accordingly, your (2) is asking whether the polynomial hierarchy collapses to NP. 3. Take a look at Neil Immerman's summary of (https://people.cs.umass.edu/~immerman/descriptive_complexity.html) and book on (https://people.cs.umass.edu/~immerman/book/ch0_1_2.pdf) descriptive complexity.  
> **username_0**: Thanks @HuckBennett that's helpful!  

---

## 0 answers

