Les preuves de complétude demandent à identifier l'espace du problème et l'espace des solutions pour ensuite montrer que l'algorithme produit bien le second à partir du premier.
le- pʁˈøv də- kɔ̃pletˈyd dəmˈɑ̃dt a idɑ̃tifjˈe lɛspˈas dy- pʁɔblˈɛm e lɛspˈas de- solysjˈɔ̃ puʁ ɑ̃syˈit mɔ̃tʁˈe kə (en)ˈɛlˈalɡɔːɹˌɪθm(fr) pʁodyˈi bjˈɛ̃ lə- səɡˈɔ̃t a paʁtˈiʁ dy- pʁəmjˈe.