------------------------------------
01. Časovno omejeni Turingovi stroji
------------------------------------
- deterministični Turingov stroj (DTM), ki se ustavi v času največ T(n), kjer je "n" dolžina vhodne besede

------------------------------
02. Razred problemov/jezikov P
------------------------------
- ko je T(n) polinomska funkcija parametra n na DTS
- primeri: 
	+ je w v G za neko KNS G?
	+ ali obstaja pot iz vozlišča x do vozlišča y v nekem grafu G?
	+ problem "pseudo nahrbtnika"

-------------------------------
03. Razred problemov/jezikov NP
-------------------------------
- ko je T(n) polinomska funkcija parametra n na NTS (nedeterminističnem Turingovem stroju)
- primer: problem "nahrbtnika"
- NP polnost

-------------------------------
04. Prevedbe v polinomskem času
-------------------------------
- polinomski pretvornik (-p->)
- uporabljamo za dokazovanje, da so določeni problemi NP polni

--------------------------------
05. NP polnost problemov/jezikov
--------------------------------
- Cook-ov teorem: SAT je NP poln problem (vsak NTS -p-> SAT)
- CSAT je NP poln problem (vsak NTS -p-> CSAT)
	+ SAT v konjunktivni normalni obliki (CNF)
	+ pretvorba v CNF
- 3-SAT je NP poln problem (CSAT -p-> 3-SAT)
- problem pokritja grafa je NP poln (3-SAT -p-> problem pokritja)
- problem nahrbtnika je NP poln (3-SAT -p-> nahrbtnik "s ciljem" -p-> nahrbtnik)

---------------------
06. NP težki problemi
---------------------
- problemi, ki ne izgledajo, da bi lahko bili v NP
- Co-NP: komplement problema je v NP
- primer: problem tavtologije logičnih izrazov je NP težek