Fogalmak:

4. Nemdeterminisztikus Turing gép:
	Nemdeterminisztikus Turing gép;
	legális számolás;
	NTIME(f(n));
	tanú (f(n) hosszúságú, g(n) idejű);
	polinomiálisan visszavezethetőség;
	NP-teljesség;
	NP-nehéz függvény;
5. Randomizált algoritmusok:
	Fermat-feltétel;
	Rabin-Miller-feltétel;
	Randomizált Turing gép;
	gyengén eldöntés (Monte-Carlo értelemben eldöntés);
	a randomizált Turing gép elfogadja a nyelvet;
	erősen eldöntés (Las Vegas értelemben eldöntés);
	BPP, RP, DeltaRP osztályok; 
6. Információs bonyolultság:
	Egy x szó bonyolultsága;
	önkorlátozó (szó);
	informatikusan véletlen sorozat;
	entrópia;
	információelméleti korlát

Tételek:
4. Nemdeterminisztikus Turing gép:
	Soroljon fel 3 NP-beli nyelvet;
	Euler's formula;
	Kuratowsk itétele;
	Frobenius tétele;
	Tutte tétele;
	Farkas Lemma;
	Cook-Levin tétel;
	Soroljon fel 3 NP-teljes problemát.
5. Randomizált algoritmusok:
	Schwartz Lemma;
	kis Fermat Tétel;
6. Információs bonyolultság:
	Invariancia tétel;
	Levin kódolási tétele;