  Results of computational complexity exist for a wide range of phrase
structure-based grammar formalisms, while there is an apparent lack of such
results for dependency-based formalisms. We here adapt a result on the
complexity of ID/LP-grammars to the dependency framework. Contrary to previous
studies on heavily restricted dependency grammars, we prove that recognition
(and thus, parsing) of linguistically adequate dependency grammars is
NP-complete.
