JFIZO - Zadanie 09.085

Jeśli A \in NP, to istnieje NTM M_A.

Maszyna niedeterministyczna podczas obliczenia korzysta z niedeterminizmu wtedy, gdy ma więcej niż jedną możliwą akcję, dla jednej konfiguracji.

Możemy zmodyfikować maszynę, aby najpierw wyznaczała sobie na taśmie pewien obszar, zapisała na nim tyle liczb, ile ma niedeterministycznych wyborów w obliczeniu. Potem przechodzimy do normalnego obliczenia. W momencie natrafienia na niejednoznaczną konfigurację, czytamy pierwszą z wylosowanych liczb od lewej, niech to będzie i, kasujemy ją i wybieramy i-tą regułę deterministycznie.

Zlozonosc M_A niech bedzie p krokow. Wtedy musimy zapisac max p komorek po |Q| (ilosc stanow) * 2 (lewo lub prawo) * ilosc_charow (bo moge zamienic to co mam na tasmie na cos innego)$ - tak?