Teoreetilibe informaatika kordamisküsimused
Ajaline keerukus algoritmi n-astmelise sisendi jaoks tehtav sammude arv f(n).
Asümptootilised hinnangud sisendandmete mahu piiramatul kasvamisel.
Polünomiaalse keerukusega algoritmid:
O(nd)
Ülesanded, mille jaoks leidub polünomiaalse keerukusega algoritm, nim reaalselt
lahenduvateks.
Keskmine ja halvim keerukus.
34. NP ja NP-täielikud ülesanded.
Ülesannete keerukuse klassid.
Põhiline on polünomiaalse keerukusega ülesannete klass reaalselt
lahenduvad.
NP mittedeterministlikult polünomiaalne. Ülesanded, mis on lahendatavad
mittedeterministlikul Turingi masinal polünomiaalse ajaga.
Nt lausearvutuse valemis true leidmine.
Seljakotiülesanne (leia max erinevaid asju seljakotti, nii, et ei ületataks kaalu).
Graafis tee leidmine Hamiltoni meetodil.
Graafis kõigi tippude läbimiseks lühima tee leidmine.
NPC klass NP ülesannete grupid, mis on taandatavad teineteisele.
Näiteks on kõik eelnevad ülesanded taandatavad seljekotiülesandele.
annaabi.ee 
