Editace stránky Složitost II

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Varování: Nejste přihlášen(a). Pokud uložíte jakoukoli editaci, bude vaše IP adresa zveřejněna v historii této stránky. Pokud se přihlásíte nebo si vytvoříte účet, budou vaše editace připsány vašemu uživatelskému jménu a získáte i další výhody.

Editace může být zrušena. Zkontrolujte a pak potvrďte změny zobrazené níže.
Aktuální verze Váš text
Řádka 624: Řádka 624:
 
Délka celé QBF má být polynomiální, stejně tak čas její konstrukce (z definice převoditelnosti). Rekurzivní algoritmus se zanoří až S(n)-krát, na každé úrovni kvantifikuje 3 nové konfigurace = 3*S(n) nových bool. proměnných. Délka této části je kvadratická. Na nejnižší úrovni (t=1) se "přilepí" QBF o velikosti přechodové funkce M.
 
Délka celé QBF má být polynomiální, stejně tak čas její konstrukce (z definice převoditelnosti). Rekurzivní algoritmus se zanoří až S(n)-krát, na každé úrovni kvantifikuje 3 nové konfigurace = 3*S(n) nových bool. proměnných. Délka této části je kvadratická. Na nejnižší úrovni (t=1) se "přilepí" QBF o velikosti přechodové funkce M.
  
Zde nastává problém, když velikost M není omezená polynomem daného vstupu (stejný problém např. u Kachlíkování, kdy se vyrábí víc kachlíků, než je polynom vstupu). Fígl je ten, že polynomiální převoditelnost je definovaná mezi dvěma jazyky, nikoli mezi třídou a jazykem. Celý postup výše nepopisuje algoritmus převodu DTS na QBF, ale jen schéma spousty různých algoritmů, každý z nich převádí slovo na QBF pro jeden konkrétní DTS v poly-čase. Krátkých vstupů (jejichž polynom nepřekročí velikost stroje) je jen konečně mnoho a můžeme pro ně vyrobit konečný automat, který pro dané vstupy vrátí "konstantní True QBF", např. <math>\forall x (x \vee \neg x) </math> (nebo konstantní false QBF, pokud dané krátké slovo automat nepřijímá).
+
Zde nastává problém, když velikost M není omezená polynomem daného vstupu (stejný problém např. u Kachlíkování, kdy se vyrábí víc kachlíků, než je polynom vstupu). Fígl je ten, že polynomiální převoditelnost je definovaná mezi dvěma jazyky, nikoli mezi třídou a jazykem. Celý postup výše nepopisuje algoritmus převodu DTS na QBF, ale jen schéma spousty různých algoritmů, každý z nich převádí slovo na QBF pro jeden konkrétní DTS v poly-čase. Krátkých vstupů (jejichž polynom nepřekročí velikost stroje) je jen konečně mnoho a můžeme pro ně vyrobit konečný automat, který pro dané vstupy vrátí "konstantní True QBF", např. <math>\forall x (x \vee \neg x) </math>.

Kliknutím na Save page

  • Potvrzujete, že vložené změny jsou vaším dílem, nebo jste oprávněni je zveřejnit a licencovat podle pravidel této stránky.
  • Potvrzujete, že smluvní podmínky níže uvedených licencí znáte a chápete, nebo se s nimi v nejbližší době seznámite.
  • Souhlasíte se zveřejněním svých změn podle licence MatfyzKing copyright
  • Souhlasíte se zveřejněním svých změn podle licence Creative Commons BY-NC-SA 2.0
  • Souhlasíte se zveřejněním svých změn podle licence GNU GFDL

Nevkládejte cizí díla bez prokazatelného souhlasu autora nebo držitelů práv!

Storno | Pomoc při editování (otevře se v novém okně)

Šablony použité na této stránce: