JFiZO - Lista 12
JFiZO - Zadanie 09.121
Musimy udowodnic, ze re = \Sigma^*.
Regexp mozemy reprezentowac w postaci NFA w liniowej pamieci (Lemma 1.29, example 1.30, example 1.31, Sipser).
JFiZO - Zadanie 09.123
Zdefiniujmy sobie 3-arnego XOR'a tak:
xor_3(x,y,z) = (x \wedge -y \wedge -z) \vee (-x \wedge y \wedge -z) \vee (-x \wedge -y \wedge z)
Teraz używamy po prostu algorytmu z zadania 126, z tym, że XOR'a 2-arnego zastępujemy 3-arnym.
JFiZO - Zadanie 09.133
R_{16}(c,k) = \exists r \forall x \forall y [ (x=c \wedge y=r) \vee (x=r \wedge y=k ) ] \Rightarrow R_8(x,y)
R_8 , R_4 - analogicznie
R_2(s,t) = \exists r R(s,r) \wedge R(r,t)
3 * 3 kwantyfikatory na R16,R8 i R4 oraz 1 na R2 dają w sumie równe 10 kwantyfikatorów
JFiZO - Zadanie 09.135
Problem opisany w zadaniu jest NP trudny. Dlaczego? Otóż pytanie, czy formuła \phi \in QBF, w której występują tylko kwantyfikatory \exists , jest prawdziwa, to właściwie pytanie, czy formuła \phi' pozbawiona kwantyfikatorów jest spełnialna. Gdy dokładamy kwantyfikatory \forall, sytuacja zmienia się. Jednak, ponieważ mamy tylko dwa takie kwantyfikatory \forall p \forall q, to możemy rozpatrzyć 4 przypadki - za każdym razem podstawiając pod p i q różne wartości sprawdzić, czy wtedy formuła \phi' jest spełnialna. A to możemy, gdy dysponujemy niedeterministyczną maszyną Turinga, zrobić w czasie wielomianowym (po prostu cztery razy „zgadując” wartościowanie i sprawdzając, czy zawsze jest prawdziwe).
