Algoritmu sarežģītība

9. lekcija

Alternējošas Tjūringa mašīnas

Apskatīsim alternējošu Tjūringa mašīnu simetrijas pazīšanai un pierādīsim, ka simetrijas pazīšanai pietiek ar lineāru darba laiku.

Sākumam apskatīsim citu valodu, kas noderēs vēlāk simetrijas apskatīšanai.

  1. Binārie skaitļi

Apskatāmā valoda četru burtu alfabētā (1, 0, 1, 0) ir (pēc kārtas visi binārie skaitļi):

0

1

0

0

0

1

1

0

1

1

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

1

…

  1. Ja grib noskaidrot, vai valoda nepieder:

    2. Tāpat kā nedeterminēta Tjūringa mašīna:

    Izvēlas vienu no fragmentiem un pārbauda vai nākošais ir pareizs:

    Lai aizietu līdz vajadzīgajam jāizlieto n soļi; lai salīdzinātu – (log n)2. Tātad kopā vajag n + (log n)2 < 2n (lineārā laikā).

  2. Ja grib noskaidrot, vai valoda pieder:

Šajā gadījumā nedeterminētai Tjūringa mašīnai nav priekšrocību salīdzinot ar determinētām mašīnām (uz katru fragmentu (skaits log n) vajag (log n)2 salīdzināšanai, kopā c n log n).

Sākumā universālā režīmā izvēlas vienu no fragmentiem, izvēlēto pārbauda un noskaidro, vai ir pareizs. Tātad kopā vajadzīgs c n.

 
  1. Simetrija

Tālāk apskatīsim simetriju, izmantosim papildceliņus (trīs). Tie nemaina sarežģītību, ja to ir konstants skaits.

Sākumā uzģenerē divas simbolu virknes četru burtu alfabētā (1, 0, 1, 0). Tādas pašas kā pirmajā piemērā. Vienu virs dotās virknes un otru zem dotās virknes (apgrieztā secībā).

  1. Eksistenciālā režīmā raksta virkni;

    2.
                                                         

    0

    1

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    0

    0

    0

    1

    0

    1

    0

    0

    1

    1

    1

    0

    0

    1

    1

    0

    1

    0

    0

    1

    1

    1

    0

    1

    1

    0

    1

    0

    0

    0

    1

    0

    1

    1

    0

    1

    1

    1

    0

    0

    1

    0

    1

    1

    0

    0

    1

    1

    1

    0

    0

    1

    0

    1

    0

    0

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    0

    1

    0

  2. Universālā režīmā izvēlas vienu no fragmentiem (tāpat kā pirmajā piemērā), ja kaut kur būs neatbilstība, tad teiks nē, un paliks viens, kur būs jā;

    3. Ja izvēlas nepareizo, tad izlieto n+(log n)2;

  3. Universālā režīmā izvēlas vienu ciparu uz vidējā celiņa un sameklē viņa numuru uz augšējā celiņa;

    4.
                                                         

    0

    1

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    0

    0

    0

    1

    0

    1

    0

    0

    1

    1

    1

    0

    0

    1

    1

    0

    1

    0

    0

    1

    1

    1

    0

    1

    1

    0

    1

    0

    0

    0

    1

    0

    1

    1

    0

    1

    1

    1

    0

    0

    1

    0

    1

    1

    0

    0

    1

    1

    1

    0

    0

    1

    0

    1

    0

    0

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    0

    1

    0

  4. Eksistenciālā režīmā raksta virkni uz paša augšējā celiņa;

  5. Universālā režīmā izvēlas vienu no fragmentiem (uz paša augšējā celiņa) un salīdzina ar nākamo fragmentu, ja nesakrīt, tad saka nē.

    6.

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    0

    0

    0

    1

    0

    1

    0

    0

    1

    1

    1

    0

    0

    1

    1

    0

    1

    0

    0

    1

    1

    1

    0

    1

    1

    0

    1

    0

    0

    0

    1

    0

    1

    1

    0

    1

    1

    1

    0

    0

    1

    0

    1

    1

    0

    0

    1

    1

    1

    0

    0

    1

    0

    1

    0

    0

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    0

    1

    0

  6. Eksistenciālā režīmā izvēlas kādu vietu uz dotā celiņa un sameklē tā atbilstošo numuru uz apakšējā celiņa. Tad to salīdzina ar tuvāko fragmentu uz paša augšējā celiņa. Noskaidro vai šie numuri ir savstarpēji apgriezti (to var izdarīt c (log n)2).

    7. 1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    1

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    0

    0

    0

    1

    0

    1

    0

    0

    1

    1

    1

    0

    0

    1

    1

    0

    1

    0

    0

    1

    1

    1

    0

    1

    1

    0

    1

    0

    0

    0

    1

    0

    1

    1

    0

    1

    1

    1

    0

    0

    1

    0

    1

    1

    0

    0

    1

    1

    1

    0

    0

    1

    0

    1

    0

    0

    0

    0

    0

    1

    1

    0

    1

    1

    0

    0

    0

    1

    0

  7. Visbeidzot salīdzina abus uz dotā celiņa izvēlētos simbolus, ja vienādi tad saka - jā, ja nav - nē.

Katrā no posmiem soļu daudzums nav lielāks par c n. Tātad kopējais soļu skaits, kas nepieciešams simetrijas pazīšanai, ir c n. Tātad simetriju var pazīt ar alternējošu mašīnu lineārā laikā.

 

Valodu klases

Ja ar Tjūringa mašīnu valodu nevar pazīt polinomiālā laikā, tad arī ne ar kādu citu nevar.

Valoda pieder klasei P, ja eksistē determinēta Tjūringa mašīna, kas šo valodu pazīst polinomiālā laikā.

Valoda pieder klasei NP, ja eksistē nedeterminēta Tjūringa mašīna, kas šo valodu pazīst polinomiālā laikā.

Valoda pieder klasei AP, ja eksistē alternējoša Tjūringa mašīna, kas šo valodu pazīst polinomiālā laikā.

Valoda pieder klasei PP, ja eksistē varbūtiska Tjūringa mašīna, kas šo valodu pazīst polinomiālā laikā ar varbūtību > 1/2.

Valoda pieder klasei BPP, ja eksistē varbūtiska Tjūringa mašīna un d > 0, ka mašīna pazīst valodu polinomiālā laikā ar varbūtību > 1/2 + d .

 

Lekciju pierakstīja R.Barkāns

romualds@di.lv

09.03.99