
## 7.3 Particular Constraints

One may consider the case where not only rules but also constraints are restricted. Let us first consider the meaningful category of negative constraints.

Theorem 13 (Complexity with negative constraints)  Without any assumption on the rules in E or R, but using only negative constraints:
- SGC-CONSISTENCY becomes co-NP-complete
- SGC-DEDUCTION becomes DP-complete
- SRC-INCONSISTENCY (SRC-CONSISTENCY co-problem) becomes semi-decidable.

- SEC-DEDUCTION remains semi-decidable.
- SRC-DEDUCTION and SREC-DEDUCTION remain truly undecidable.

Proof:
Co-NP-completeness of SGC-CONSISTENCY: from NP-completeness of projection checking (th. 8).

DP-completeness of SGC-DEDUCTION: this problem can be expressed as "is it true that Q can be projected into G and that no constraint of C can be projected into G ?"  thus belongs to DP. Now let us consider that C contains only one constraint.  A reduction from 3-SAT to PROJECTION (see f.i. the proof of th. 2) provides a straightforward reduction from SAT/UNSAT to SGC-DEDUCTION (see f.i. Papadimitriou, 1994), thus the DP-completeness.

Semi-decida bility of SRC-INCONSISTENCY:  To prove the inconsistency of a KB, we must find some violation of a constraint that will never be restored.  But no violation of a negative constraint can ever be restored (further rule applications can only add information, thus more possible projections, and cannot remove the culprit one). So we only have to prove that one constraint of C can be deduced from ( G, R ): it is a semi-decidable problem. Undecidability of SRC-DEDUCTION follows: we must prove that Q can be deduced from ( G,R), but that no constraint of C can.

The arguments proving semi-decidability of deduction in SEC and undecidability of deduction in SREC are the same as the ones used in the proof of Th. 10.

□
The restriction to negative constraints decreases complexity of problems in the SGC
model, but it does not help much as soon as rules are involved, since these problems remain undecidable.  Combining range restricted rules and negative constraints, we obtain more interesting complexity results:
Theorem 14 (Complexity with r.r. rules and negative constraints) If only rangerestricted rules and negative constraints are present in the knowledge base:
- SRC-CONSISTENCY becomes co-NP-complete
- SRC-DEDUCTION becomes DP-complete
- SEC-DEDUCTION and SREC-DEDUCTION become E, -complete