P vs NP Flashcards
1
Q
Definuj polynomiálne rozhodnuteľnú reláciu, polynomiálne vyváženú
A
str. 45
2
Q
Dokáž lemu o príslušnosti jazyka do NP a existencii polynomiálnych relácií
A
str. 45
3
Q
Dokáž, že nie je možné aby P!=NP a NPU=NP-P (vyslov vetu a dokáž)
A
Ladnerova veta: Ak P != NP, tak existuje jazyk L ∈ NP taký, že L !∈ P a L !∈ NPU.
dôkaz 46, resp. alternatívny 5.1.2
4
Q
Definuj TS s orákulom
A
str. 48
5
Q
Definuj pre C=DTIME(f(n)) a jazyk A C^A
A
str. 48
6
Q
Ako vieme pomocou orákula definovať problém P?=NP?
A
Otázka P^A=NP^A kde A je prázdna množina
7
Q
Prečo to nie je ľahké dokázať pomocou orákula? (P a NP)
A
lebo existuje orákulum A a B t.ž. P^A=NP^A a P^B != NP^B, teda nevieme povedať ako to je pre prázdnu mn.
8
Q
Dokáž, že existuje orákulum A t.ž. P^A=NP^A
A
str. 48
