On montre que le problème du rendu de monnaie est NP-difficile par Réduction à partir du problème du sac à dos.
1	On	on	PRON	_	Gender=Masc|Number=Sing|Person=3|PronType=Ind	2	nsubj	_	wordform=on
2	montre	montrer	VERB	_	Mood=Ind|Number=Sing|Person=3|Tense=Pres|VerbForm=Fin	0	root	_	_
3	que	que	SCONJ	_	_	12	mark	_	_
4	le	le	DET	_	Definite=Def|Gender=Masc|Number=Sing|PronType=Art	5	det	_	_
5	problème	problème	NOUN	_	Gender=Masc|Number=Sing	12	nsubj	_	_
6-7	du	_	_	_	_	_	_	_	_
6	de	de	ADP	_	_	8	case	_	_
7	le	le	DET	_	Definite=Def|Gender=Masc|Number=Sing|PronType=Art	8	det	_	_
8	rendu	rendu	NOUN	_	Gender=Masc|Number=Sing	5	nmod	_	_
9	de	de	ADP	_	_	10	case	_	_
10	monnaie	monnaie	NOUN	_	Gender=Fem|Number=Sing	8	nmod	_	_
11	est	être	AUX	_	Mood=Ind|Number=Sing|Person=3|Tense=Pres|VerbForm=Fin	12	cop	_	_
12	NP-difficile	NP-difficile	ADJ	_	Gender=Masc|Number=Sing	2	ccomp	_	wordform=np-difficile
13	par	par	ADP	_	_	14	case	_	_
14	Réduction	réduction	NOUN	_	Gender=Fem|Number=Sing	12	obl:mod	_	wordform=réduction
15	à	à	ADP	_	_	14	advmod	_	ExtPos=ADV|Idiom=Yes
16	partir	partir	VERB	_	VerbForm=Inf	15	fixed	_	InIdiom=Yes|Subject=Generic
17-18	du	_	_	_	_	_	_	_	_
17	de	de	ADP	_	_	19	case	_	_
18	le	le	DET	_	Definite=Def|Gender=Masc|Number=Sing|PronType=Art	19	det	_	_
19	problème	problème	NOUN	_	Gender=Masc|Number=Sing	15	obl:arg	_	_
20-21	du	_	_	_	_	_	_	_	_
20	de	de	ADP	_	_	22	case	_	_
21	le	le	DET	_	Definite=Def|Gender=Masc|Number=Sing|PronType=Art	22	det	_	_
22	sac	sac	NOUN	_	Gender=Masc|Number=Sing	19	nmod	_	_
23	à	à	ADP	_	_	24	case	_	_
24	dos	dos	NOUN	_	Gender=Masc|Number=Sing	22	nmod	_	SpaceAfter=No
25	.	.	PUNCT	_	_	2	punct	_	_
