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