I have just finished an exam and there was a question I just couldn't answer. So out of curiosity I'd like to know how you people would answer it?
The question was similar to this:
"Talk about the implications regarding computational complexity when using first order predicate logic to model relationships between concepts"
I thank you in advance for any useful replies given.
Well, I would first point out that the central question that you will get: "does this statement follow from these statements" has no general computational solution, as it is, like the halting problem, undecidable.
Second, assuming that you do have some decent algorithm that can figure out 'a good number of' (but again, necessarily not all) such questions of logical consequence, the computational complexity can very quickly go up. If you just think of the truth-functional case, it is already exponential (i.e. non-polynomial .. think truth-tables!), and so if we add quantifiers, things are going to get even worse, as for each additional constant you introduce (and you don;t know how many you have to introduce ... and it may be 'a good number of those' before you get your answer), your search space increases exponentially as a further function of how many predicates you can fill in that constant with. In sum: things very quickly go 'very bad' as far as computational complexity goes. This is why automated theorem provers are still a long way of from being able to prove theorems in mathematics without some serious human assistance.