Prezydent: Podjąłem decyzję ws. ustaw zdrowotny...

[funny5]

Klasyczne wiem ale nie powiem

Prezydent powinien pisac scenariusze seriali

[jankbh]

Znowu "wiem, ale nie powiem", maluczkim laskawie tylko przekazal, ze
jest i ma wladze.

Prezydencie! 85% Polaków ma cie w nosie !

[jama.314]

wetuj sobie...

Wiem, ale nie powiem (ze złożoności obliczeniowej)

[skubi6]

Mam dwa grafy G1 i G2. Wiem, że są izomorficzne i znam odpowiednie odwzorowanie
(izomorfizm) wierzchołków G1 na wierzchołki G2, tzn. taką permutację
wierzchołków G1, że jak ją zastosujemy, to z G1 robi się G2.

Jeśli ktoś tego izomorficmu nie zna, to odnalezienie go jest NP-zupełne
(praktycznie: nie do zrobienia), więc znajomość izomorfizmu jest cenna, kto tej
wiedzy nie ma, ten łatwo jej nie zdobędzie. Można tę wiedzę używać do
rozróżniania między wtajemniczonymi a niewtajemniczonymi.

Jak dowieść komuś, że ten izomorfizm znam, a jednocześnie go nie wyjawić?

Robimy dialog, który powtarzamy do woli:

Losuję permutację wierzchołków G1 (zupełnie dowolną, przypoadkową). Taka
permutacja przekształca G1 w nowy graf G3. Przekazuję niedowiarkowi G3 (nie
premutację, tylko graf G3, który wychodzi z permutacji; niedowiarek nie wie,
jaką permutacją uzyskano G3 z G1) i twierdzę, że znam izomorfizm G1->G3->G2
(G1->G3, to właśnie moja permutacja, a G3->G1 to tajemny, znany mi izomorfizm
G2->G1 złożny z odwróceniem tej permutacji).

Niedowiarek może zarządać ode mnie albo G1->G3, albo G3->G2, ale nie obu. Gdybym
dał mu oba, to mógłby je złożyć i uzyskać tajemny izomorfizm G1->G2, a ja mu nie
chcę właśnie tego izomorfizmu dać.

Gdybym kłamał (tzn. gdybym nie znał izomorfizmu G1->G2), to bym nie był w stanie
podać albo G1->G3, albo G3->G2. A więc niedowiarek, który rząda G1->G3 albo
G3->G2 z prawdopodobieństwem 50% miałby szansę się przekonać, że kłamię.

Taki dialog powtarzamy tyle razy, ile trzeba, aż niedowiarek w końcu dojdzie do
wnisku, że znamy G1->G2 (ma dowolnie wiele niezależnych prób, w każdej ma 50%
szansy wykrycia, że kłamię, jeśli rzeczywiście kłamię).

To wszystko jest ciekawe, ale chyba za trudne dla Pana Prezydenta. Ale może ktoś
wydrukuje ten wpis i go prześle do Kaczego Pałacu, żeby kaczor (który bądź co
bądź jest profesorem) nauczył się mówić "wiem, ale nie powiem" uczenie. Wtedy
nawet informatycy na niego zagłosują.

www.skubi.net/macierewicz.html
www.skubi.net/pieniadz.html

Kaczynski = Lepper=Rydzyk=Oszolom

[wrojoz]

nie moge sie doczekac!!!

[dalatata]

drze w niepewnosci! Panie prezeydencie, niech pan choc powie jutro, we wtorek.
no wiecozrem chociaz!!! nooooooooooo!!!!! panie prezydencie!!!!

[tom.te]

No przecież sie musi spytać Prezesa czy aby na pewno podjął prawidłową decyzję.

Kaczynski to truten.

[wrojoz]