Nedeterminisma maŝino de Turing
En teorio de komputado, nedeterminisma maŝino de Turing estas maŝino simila al maŝino de Turing, sed por kiu, en iuj okazoj, povas esti difinita pli ol unu varianto de la konduto.
La elekto de konduto en ĉi tia nedeterminisma okazo estas nomata kiel preno de konsilo de orakolo.
Malsimile al determinisma maŝino de Turing kiu havas nur unu vojon de kalkulado, nedeterminisma maŝino de Turing havas arbon de la vojoj. Nedeterminisma maŝino de Turing akceptas la enigon se iu el branĉoj de la arbo haltiĝas je la akcepta stato aŭ alivorte redonas jesan respondon. Tiel, la nea kaj jesa respondo ne estas simetriaj por ĉi tia maŝino. Eblas diri, ke ĝia respondo estas logika aŭo de respondoj de ĉiuj branĉoj, kaj eĉ unu "jes" sufiĉas por ke estu entuta "jes".
Kiel nedeterminisma maŝino de Turing elektas kiu el la eblaj variantoj donas akcepton de la enigo:
- Eblas konsideri, ke ĝi estas ĉiam bonŝanca, do ĝi ĉiam elektas tiun varianton kiu rezultiĝas je akcepto de la enigo, se ĉi tia varianto ekzistas (konsilas kun bona orakolo).
- Eblas konsideri, ke en ĉiu okazo kiam estas pli ol unu varianto ĝi faras kopiojn de si, kaj la malsamaj kopioj laboras plu laŭ ĉiu el la eblaj variantoj. Poste ĉiu el la kopioj denove povas disdividiĝi, kaj la kvanto de funkciantaj kopioj povas kreski eksponente kun tempo.
Nedeterminisma maŝino de Turing povas esti modelata per determinisma maŝino de Turing per kreo kaj laŭvica prilaboro de kopioj de la modelata maŝino. Ĉi tiu modelado povas bezoni eksponente pli grandan rultempon.
Ekzemplo[redakti | redakti fonton]
Estu decida problemo de kontrolo ĉu donita b-bita entjero N (2b-1≤N<2b) estas komponigita. Tiel b estas la longo de la enigo, respektive al kiu estas konsiderata la rultempo. La respondo estas "jes" - komponigita nombro kaj "ne" - primo. La problemo estas komplemento al primeco-testo.
La nedeterminisma algoritmo por la tasko povas esti jena:
- Elekti iel (nedeterminisme) entjeron m tian ke 1<m<N.
- Dividi N per m kaj la restaĵo estu a.
- Se a=0 do redoni respondon "jes" (m estas tiam trovita divizoro de N), alie redoni respondon "ne".
La algoritmo ne estas skribita en stilo de maŝino de Turing, tamen ĉi tio ne gravas.
En rultempo de la algoritmo la plej grandan parton prenas la divido, kiu povas esti plenumita en O(b2) paŝoj, kio estas polinoma tempo. Tiel la problemo estas en komplikeca klaso NP - ĝuste klaso de problemoj kiuj povas esti solvitaj per nedeterminisma maŝino de Turing en polinoma tempo.
Por realigi la malgrandan tempon de kalkulado, necesas bonŝance elekti la nombron m, aŭ reale kalkuli ĉiujn vojojn (por ĉiuj eblaj m) samtempe en kopioj de la maŝino.
Tamen, se modeli la algoritmon per determinisma maŝino de Turing per provado de ĉiuj eblaj vojoj de la kalkulado, necesas provi N-2=O(2b) vojojn. Entute la rultempo tiam estas O(b22b) paŝoj, kio estas jam eksponenta tempo, kio estas signife pli granda ol la polinoma tempo. Tiel ĉi tiu algoritmo ne estas en komplikeca klaso P - ĝuste klaso de problemoj kiuj povas esti solvitaj per determinisma maŝino de Turing en polinoma tempo. (Tamen, per elekto de pli kompetenta algoritmo, la problemo estas en la klaso P.)
Vidu ankaŭ en:
- primeco-testo pri kompetentaj algoritmoj por la problemo
- Demando P = NP pri komparo de la klasoj P kaj NP