There are two kinds of problems in the AI world:
the naughty and the nice. The naughty problems are those
where everything depends on everything else. The N-Queens problem in
Figure 26 is
a good example. Even if some poor unfortunate is able to place N-1
Queens legally, placement of the 
Queen can be foiled by any of
the N-1 already placed. These naughty problems typically are what
people have in mind when they think about CSPs. Massive amounts of
constraints going every which way. Look at just about any CSP
reference (for example, [Tsang, 1993]) and you will see a
preponderance of problems for which there will be no presents under
the tree.
Figure 26: The 8-Queens Problem
Fortunately (or perhaps unfortunately - see below), real world
problems are not naughty, but nice.
Often a real world problem gains its complexity not from dense
interconnections of constraints, but simply from the large number of
possible solutions. Natural Language is a perfect example of the latter.
Given a sentence of length 23 (an
average-looking sentence), and assuming each word can have two
meanings, this yields
possible combinations of word senses, or over eight million.
As strange as it may seem, though, in the CSP world ``naughty'' problems are actually ``nice,'' and ``nice'' problems can be extremely ``naughty.'' Figure 27 reproduces a table from [Tsang, 1993]. ``Naughty'' problems are those on the right-hand side, tightly constrained. For a human, keeping track of a large number of interacting constraints makes the problem difficult, that is why we tend to think of them as ``naughty.'' For a computer, though, the constraints actually help, using CSP, to make the problem easier. The loosely constrained problems on the left side for which all solutions are required from among a large set of possible solutions are described in the table as ``hard by nature.''
The first major point of this research is to show that computational semantic problems
are, in fact ``naughty,'' and thus are ``nice'' in the CSP world.
More precisely, we will demonstrate that computational semantic problems are tightly
constrained locally, and CSP techniques can be used to great
advantage in identifying these local interactions and determining
their solutions. Perhaps even more important,
we can use the fact that certain parts of the problem are not
constrained to guide
solution synthesis most efficiently.
Another aspect of computational semantics that can cause problems with regard to applying CSP techniques is the fact that the constraints often do not have ``yes'' or ``no'' answers. CSP relies on definite answers to prune away inconsistent solutions. In natural language semantics, however, nothing is ever straightforward. Is the ``White House'' a HUMAN? No, it is a building, and yet we can say ``The White House said today that ...'' without even thinking about calling the Ghost Busters. Does this eliminate computational semantics from the domain of CSP problems? In one sense, it does. A straightforward application of CSP consistency algorithms would yield little, since constraints in are only tendencies; metonymy and figurative language often override these tendencies. However, branch-and-bound techniques combined with solution synthesis can be used to efficiently drive an computational semantic search engine. The efficiency, though, as shown above, is derived from information gained by analyzing constraint dependencies. This is the second major point of this research: that the branch-and-bound / solution synthesis paradigm is a type of constraint analysis problem, with its efficiency coming from analysis of dependencies within the problem.
Finally, we demonstrated that one of the central tools in Natural Language Generation, the means-end planner, can be more efficiently implemented by framing the planning process in terms of a CSP, and then using straightforward CSP consistency algorithms to determine possible solutions. This is the third, and last, major point of this work. Thus, the computational semantic problem itself, as well as one of the major tools used in solving it, can best be seen as being a type of CSP. It's a ``natural'' fit.
