Potpunost

Potpunost može značiti:

---

U matematici i srodnim tehničkim poljima, matematički je objekt potpun (kompletan) ako mu se ništa ne može dodati. Ovo se precizira na različite načine, od kojih neki imaju povezan koncept potpunosti. Termin "potpun" ovdje samo poprima specifična značenja u specifičnim situacijama, i nije svaka situacija u kojoj se dogodi neki tip "kompletiranja" nazvana "potpunost". Vidjeti, na primjer, algebarski zatvoreno polje, kompaktifikacija, Gödelov teorem potpunosti, Gödelov teorem nepotpunosti.

---

• potpun graf, u teoriji grafova, neusmjeren graf u kojem svaki par vrhova ima točno jedan povezujući brid.
• potpuna teorija, u matematičkoj logici, teorija je potpuna, ako sadrži ili $S$ ili$\neg S$ za svaku rečenicu $S$ u jeziku. Sustav je konzistentan ako nikad ne postoji dokaz i za P i za ne P. Gödelov teorem nepotpunosti kaže da ne postoji sustav moćan kao i Peanovi aksiomi koji može biti i konzistentan i potpun.
• potpun (složenost), u računskoj teoriji složenosti, problem P je potpun za klasu složenosti C, pod danim tipom svođenja, ako je P u C, i svaki problem u C se svodi na P koristeći to svođenje. Na primjer, svaki problem u klasi NP-potpun je potpun za klasu NP, pod vremenski polinomnim, mnogo-jedan svođenjem.

• Postupak odluke (ili algoritam odluke, vidi problem odluke) je potpun ako, kadgod je odgovor "da", algoritam ga ispravno nađe. Suvisao (sound) je, ako svaki put kad algoritam odgovori "da", to je ispravan odgovor.