La preuve de complétude garantit que, pour un espace de problèmes donné, l'algorithme, s'il termine, donnera l'ensemble des solutions de l'espace du problème.
la- pʁˈøv də- kɔ̃pletˈyd ɡaʁɑ̃tˈi kˈə, puʁ œ̃n ɛspˈas də- pʁɔblˈɛm dɔnˈe, (en)ˈɛlˈalɡɔːɹˌɪθm(fr), sil tɛʁmˈin, dɔnʁˈa lɑ̃sˈɑ̃bl de- solysjˈɔ̃ də- lɛspˈas dy- pʁɔblˈɛm.