It seems like a bit much to hope to understand and verify the proof without a huge investment of time and effort. The problem is exponentially compounded if you don't already do research in theoretical computer science and have the appropriate logic background.
But! All of this has put a spotlight on a theorem that I had somehow never appreciated. It is a beautiful theorem that is well within reach of a mathematically-literate computer scientist: P = FO(LFP) over finite ordered structures. If you start reading up on this, it's immediately clear that this is interesting, because FO(LFP) say nothing a priori about computational resources in the sense that P does.
Anyway, a sufficiently curious reader can look it up as theorem 4.10 in the following text:
But! All of this has put a spotlight on a theorem that I had somehow never appreciated. It is a beautiful theorem that is well within reach of a mathematically-literate computer scientist: P = FO(LFP) over finite ordered structures. If you start reading up on this, it's immediately clear that this is interesting, because FO(LFP) say nothing a priori about computational resources in the sense that P does.
Anyway, a sufficiently curious reader can look it up as theorem 4.10 in the following text:
http://www.amazon.com/Descriptive-Complexity-Texts-Computer-...
That book is pretty light on the basics of logic. I used this book:
http://www.amazon.com/Mathematical-Logic-Undergraduate-Texts...