Property 12 Under the assumption that the maximum arity of relation types is a constant, given a range restricted set of rules R , the length of an R -derivation from G is polynomially related to the size of (G,R).

In what follows, we assume that the arity of relation types is bounded by a constant.

Theorem 12 (Complexity with range restricted rules)  When E and R are range restricted rules:
- Deduction in SR is NP-complete
- Consistency and deduction in SRC are Π 2 -complete.

- Deduction in SEC and SREC is EP-complete.

Proof: The following results heavily rely on Prop. 12: all derivations involved being of polynomial length, they admit a polynomial certificate (the sequence of projections used to build the derivation).

NP-completeness of SR-DEDUCTION . The problem belongs to NP. Indeed, a polynomial certificate is given by a derivation from G to a graph G f , followed by a projection from the goal to G ′ . When R = 0 , one obtains SG-DEDUCTION (projection checking), thus the NP-completeness.

Π -completeness of SRC-consistency and SRC-deduction. Recall the consistency check involves the irredundant form of G . In order to lighten the problem formulation, we assume here that all SGs are irredundant, but irredundancy can be integrated without increasing the consistency check complexity: see the proof of theorem 8. SRC-CONSISTENCY
belongs to Π i since it corresponds to the language L = { x | ∀ y 1 ∃ y 2 R( x, y 1, y 2 )}, where x encodes an instance ( G ; R ; C ) of the problem and ( x, y 1 ; y 2 ) E R iff y 1 = ( d 1 ; π 0 ), where d 1 is a derivation from G to G 1 , π 0 is a projection from the trigger of a constraint C i (0)
into G ′ , y 2 = ( d 2 ; π 1 ), d 2 is a derivation from G ′ to G ′′ and π 1 is a projection from C i into G s s t t 1 [ C i ( )] = π o . R is polynomially decidable and polynomially balanced (since the lengths of d 1 and d 2 are polynomial in the size of the input). When R = 0, one obtains the problem SGC-CONSISTENCY, thus the Π f -completeness.  Since SRC-DEDUCTION consists in solving two independent problems, SRC-CONSISTENCY (II)-complete) and SR-DEDUCTION
(NP-complete), and since NP is included in Π f , SRC-DEDUCTION is also Π f -complete.

E -completeness of SEC-DEDUCTION . As for SRC (see above), we assume that all SGs are irredundant. The question is "are there a derivation from G to a SG G ′ and a projection from Q into G i , such that for all G i of this derivation, for all constraint C i , for all projection π from C i (0) into G i , there exists a projection π ′ from C i into G i s.t. π ′ [ C i (0) ] = π ? ′′ . R
is polynomially decidable and polynomially balanced (since the size of the derivation from G to G ′ is polynomially related to the size of the input). Thus, SEC-DEDUCTION is in Σξ . In order to prove the completeness, we build a reduction from a special case of the problem B 3 , where the formula is a 3-CNF (i.e. an instance of 3-SAT): given a formula E, which is a conjunction of clauses with at most 3 literals, and a partition { X 1 , X 2 , X 3 } of its variables, does there exist a truth assignment for the variables in X 1 , such that for all truth assignment for the variables of X 2 , there exists a truth assignment for the variables of X 3 such that E is true? This problem is Σ -complete (Stockmeyer, 1977, theorem 4.1). Let us call it 3-SAT 3 .