| << Prev | - Up - |
As we have seen above, we can solve a domiance constraint by a `generate and test' algorithm. There is an exponential number of combinations to generated each of which can be tested in polynomial time.
If we would have an oracle guessing the right combination then we could solve the problem in polynomal time (but of course there is no such oracle). This view show that the satisfiablity of a dominance constraint can be tested in non-deterministic polynomial time algorithm. In terms of complexity theory, one says that the problem is in NP.
But the situation is even worse than one might hope at first sight. In fact satisfiability of dominance constraints is NP-complete. Thus, we cannot expect any deterministic polynomial algorithm to exist without winning the Turing award.
So do we have to give up at this point?
No, we just have to give up `generate and test'. If we cannot solve dominance constraints efficiently in all cases then we can still hope for an algorithm that is efficient for the applications to semantic underspecification.
| << Prev | - Up - |