Labeling Problems in Truth Maintenance Systems

摘要

Alone with a new and simple NP-completeness proof of the general labeling problem for Truth Maintenance Systems we discuss some special cases and give some methods to determine an upperbound for the possible number of inbeing for a given TMS. We use some affiant Algoritlims to estimable this number and we expect to use these algorithms in relabeling TMS networks.