JFiZO - Zadanie 87

Z tresci zadania:

  • B \in NP
  • p - wielomian
  • A \subset N^2, A \in P
  • B = \{n: \exists m: |m| \le p(|n|), (n,m) \in A\}

Miejmy:

  • M_B - niedeterministyczna machina turinga rozstrzyga przynaleznosc do tego zbioru.

M_B determinuje przynaleznosc n do zbioru B zgadujac ciag stanow przez ktore przechodzi. Stanow w tym ciagu jest conajwyzej p(|n|) (z definicji przynaleznosci do NP). Ten ciag stanow mozemy zakodowac jako ciag liczb naturalnych. Ten ciag liczb naturalnych mozemy zakodowac jako liczba naturalna. Niech ta liczba to m. Jesli wiec (n,m) \in A. Znamy wiec sekwencje stanow przez ktora musimy przejsc, mozemy wiec w wielomianowym czasie rozstrzygnac zbior A.

Stanow niech bedzie s. Elementow w ciagu stanow e. Niech na kazdym kroku podejmujemy decyzje ktory z s stanow niedeterministycznie wybrac. Wtedy mamy max s*e wyborow. Jest to wielomianowa liczba wyborow. p = s*e.

 
jfizo/zadanie09.087.txt · ostatnio zmienione: 2010/05/10 10:19 przez d
 
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji:MIT License
Recent changes RSS feed