Cannibals And Missionaries

• http://www-formal.stanford.edu/jmc/circumscription/node3.html
• http://www.cc.gatech.edu/~jimmyd/summaries/amarel1968-1.html

The GingerFactor on that second paper reaches the theoretical limit before the end of the abstract.

---

Well then let's try a little ProblemReformulation? of our own: is a problem hard because of something about the underlying ontology it represents, or is it hard because the way it's represented is inefficient? ContraintProblemReformulation? began with SaulAmarel's suggestion that it's the inefficiency of representation that makes problems hard. Specifically, Amarel has reformulated the problem so that it has become CombinatoriallyComplete.

In the limit, if we could reformulate all problems into simple combinatorial set theory, then all problems could be solved in a single step a la CannibalsAndMissionaries. But there are no known systematic generalizations of doing this ... and it may be that the problem of reformulation itself is NpComplete. Or worse.