Prompted by Vinay Deolalikar's purported proof of P != NP, I've been reading up on Descriptive Complexity for some background material.
The major successes of Descriptive Complexity include Fagin's result that $NP=SOexists$ (that is, the class NP is equal to the class of models of a second-order existential query over some vocabulary), and also that $P = FO(LFP)$ (that the class P is equal to the class of models of first-order queries that might use a Least-Fixed-Point operator), and also $PH = SO$.
My understanding of mathematical logic is quite shaky, but from what I understand, second-order formulas are not expressible in first order logic - how does this fact stand in relation to the results I mentioned above? Why does it not separate NP from P, or PH from P?
No comments:
Post a Comment