Tractability

• One of the problems with reasoning is that the more effective your reasoning system is, the harder it is to compute.
• Brachman and Levesque call this the tradeoff between expressiveness and tractability.
• Highly expressive languages (like second order logic) are too expensive to use generally.
• So, one has to consider this tradeoff when building a system.
• What can often happen is your system just runs out of time.
• Of course, this is a problem for natural intelligent systems too.