Complexity

• One thing we need to note about these logics is complexity.
• How long does it take to derive new facts?
• Of course, for a particular fact, depending how you program it, any logic can give a quick answer.
• However, with complexity, we are usually interested in average or worse case scenarios.
• FOPL (which seems to be called second order logic now) is NP complete.
• That means as the number of atoms grows, the time to prove in that system (in the worst case) grows like 2^n.
• In general, this makes the system impractical for any but small n.
• Moreover, as logics get more expressive, they (in general) become more complex and harder to solve.