Es gehört zu den 21 klassischen NP - vollständigen Problemen, von denen Richard M. Karp 1972 gezeigt hat, dass sie NP - vollständig sind.
1	Es	es	PRON	PPER	Case=Nom|Gender=Neut|Number=Sing|Person=3|PronType=Prs	2	nsubj	_	_
2	gehört	gehören	VERB	VVFIN	Mood=Ind|Number=Sing|Person=3|Tense=Pres|VerbForm=Fin	0	root	_	_
3	zu	zu	ADP	APPR	_	10	case	_	_
4	den	der	DET	ART	Case=Dat|Definite=Def|Number=Plur|PronType=Art	10	det	_	_
5	21	21	NUM	CARD	NumType=Card	10	nummod	_	_
6	klassischen	klassisch	ADJ	ADJA	Case=Dat|Degree=Pos|Gender=Neut|Number=Plur	10	amod	_	_
7	NP	NP	PROPN	NN	Case=Dat|Gender=Neut|Number=Plur	10	amod	_	NamedEntity=Yes
8	-	-	PUNCT	$(	_	9	punct	_	_
9	vollständigen	vollständig	ADJ	ADJA	Case=Dat|Degree=Pos|Gender=Neut|Number=Plur	7	flat	_	_
10	Problemen	Problem	NOUN	NN	Case=Dat|Gender=Neut|Number=Plur	2	obl	_	SpaceAfter=No
11	,	,	PUNCT	$,	_	18	punct	_	_
12	von	von	ADP	APPR	_	13	case	_	_
13	denen	der	PRON	PRELS	Case=Dat|Number=Plur|PronType=Rel	18	obl	_	_
14	Richard	Richard	PROPN	NE	Case=Nom|Gender=Masc|Number=Sing	18	nsubj	_	NamedEntity=Yes
15	M.	M.	PROPN	NE	Case=Nom|Gender=Masc|Number=Sing	14	flat	_	NamedEntity=Yes
16	Karp	Karp	PROPN	NE	Case=Nom|Gender=Masc|Number=Sing	14	flat	_	NamedEntity=Yes
17	1972	1972	NUM	CARD	NumType=Card	18	obl	_	_
18	gezeigt	zeigen	VERB	VVPP	VerbForm=Part	10	acl	_	_
19	hat	haben	AUX	VAFIN	Mood=Ind|Number=Sing|Person=3|Tense=Pres|VerbForm=Fin	18	aux	_	SpaceAfter=No
20	,	,	PUNCT	$,	_	23	punct	_	_
21	dass	dass	SCONJ	KOUS	_	23	mark	_	_
22	sie	sie	PRON	PPER	Case=Nom|Gender=Fem|Number=Sing|Person=3|PronType=Prs	23	nsubj	_	_
23	NP	NP	PROPN	NE	Case=Nom|Number=Sing	18	ccomp	_	NamedEntity=Yes
24	-	-	PUNCT	$(	_	25	punct	_	_
25	vollständig	vollständig	ADJ	ADJD	Degree=Pos	23	flat	_	_
26	sind	sein	AUX	VAFIN	Mood=Ind|Number=Plur|Person=3|Tense=Pres|VerbForm=Fin	23	cop	_	SpaceAfter=No
27	.	.	PUNCT	$.	_	2	punct	_	_
