Unárský jazyk - Unary language

v teorie výpočetní složitosti, a unární jazyk nebo shodný jazyk je formální jazyk (sada struny ) kde všechny řetězce mají tvar 1k, kde „1“ může být libovolný pevný symbol. Například jazyk {1, 111, 1111} je unární, stejně jako jazyk {1k | k je primární }. The třída složitosti všech těchto jazyků se někdy nazývá TALLY.

Název „unární“ pochází ze skutečnosti, že unární jazyk je kódováním sady přirozená čísla v unární číselná soustava. Protože vesmír řetězců nad jakoukoli konečnou abecedou je a spočetná sada, každý jazyk lze mapovat na jedinečnou množinu A přirozených čísel; tedy každý jazyk má unární verze {1k | k v}. Naopak, každý unární jazyk má kompaktnější binární verzi, sadu binárních kódování přirozených čísel k tak, že 1k je v jazyce.

Protože složitost se obvykle měří z hlediska délky vstupního řetězce, unární verze jazyka může být „jednodušší“ než původní jazyk. Například pokud lze jazyk rozpoznat v O (2n) čas, jeho unární verzi lze rozpoznat v O (n) čas, protože n se exponenciálně zvětšila. Obecněji řečeno, pokud lze jazyk rozpoznat v O (f (n)) čas a O (g (n)) prostor, jeho unární verzi lze rozpoznat v O (n + f (log n)) čas a O (g (log n)) prostor (požadujeme O (n) čas na přečtení vstupního řetězce). Pokud však členství v některém jazyce je nerozhodnutelný, pak je členství v jeho unární verzi také nerozhodnutelné.

Vztahy k jiným třídám složitosti

TALLY je obsažen v P / poly—Třída jazyků, které lze rozpoznat v polynomiálním čase na základě poradenské funkce, která závisí pouze na délce vstupu. V tomto případě je požadovaná poradenská funkce velmi jednoduchá - vrací jeden bit pro každou vstupní délku k upřesnění, zda 1k je v jazyce nebo ne.

Unární jazyk je nutně a řídký jazyk, protože pro každého n obsahuje maximálně jednu hodnotu délky n a nanejvýš n maximální hodnoty délky n, ale ne všechny řídké jazyky jsou unární; tím pádem TALLY je obsažen v NÁHRADNÍ.

Předpokládá se, že neexistují žádné NP-tvrdé unární jazyky: pokud existuje unární jazyk, který je NP-kompletní, pak P = NP.[1]

Tento výsledek lze rozšířit na řídké jazyky.[2]

Li L je tedy unární jazyk L * (dále jen Kleene hvězda z L) je běžný jazyk.[3]

Tally tříd

Třída složitosti P1 je třída unárních jazyků, které lze rozpoznat pomocí polynomiálního Turingova stroje (vzhledem k jeho vstupu zapsanému v unární podobě); je to analogie třídy P. Analog z NP v unárním nastavení je NP1. A počítání třída #P1, analog z #P, je také známý.[4]

Reference

Poznámky

  1. ^ Piotr Berman. Vztah mezi hustotou a deterministickou složitostí NP-úplných jazyků. v Sborník z 5. konference o automatech, jazycích a programování, str. 63–71. Springer-Verlag. Přednášky z informatiky # 62. 1978.
  2. ^ S. R. Mahaney. Řídké kompletní sady pro NP: Řešení domněnky od Bermana a Hartmanise. Journal of Computer and System Sciences 25:130-143. 1982.
  3. ^ -, Patrick. „Hvězda Kleene nekonečného unárního jazyka vždy přináší běžný jazyk“. Computer Science Stack Exchange. Citováno 19. října 2014.CS1 maint: číselné názvy: seznam autorů (odkaz)
  4. ^ Leslie Valiant, Složitost výčtu a problémy se spolehlivostí, [1] uzavřený přístup

Obecné odkazy