Obvody přes množiny přirozených čísel - Circuits over sets of natural numbers

Obvody přes přirozená čísla jsou matematický model používaný při studiu teorie výpočetní složitosti. Jsou to zvláštní případ obvodů. Objekt je označen štítkem směrovaný acyklický graf jejichž uzly se hodnotí na množiny přirozených čísel, listy jsou konečné množiny a brány jsou množinové operace nebo aritmetické operace.

Jako algoritmické Úkolem problému je zjistit, zda je dané přirozené číslo prvkem výstupního uzlu nebo zda dva obvody počítají stejnou množinu. Rozhodnutelnost je stále otevřenou otázkou.

Formální definice

Přirozený číselný obvod je a obvod, tj. označený směrovaný acyklický graf stupně nanejvýš 2. Uzly stupně 0, listy, jsou konečné množiny přirozených čísel, popisky uzlů stupně 1 jsou -, kde ${ displaystyle { overline {A}} = {x v mathbb {N} | x ne v A }}$ a popisky uzlů stupně 2 jsou +, ×, ∪ a ∩, kde ${ displaystyle A + B = {a + b | a v A, b v B }}$, ${ displaystyle A krát B = {a krát b | a v A, b v B }}$ a ∪ a ∩ obvyklým způsobem soubor význam.

Rovněž je studována podmnožina obvodů, které nepoužívají všechny možné štítky.

Algoritmické problémy

Lze se zeptat:

• Je dané číslo n člen výstupního uzlu.
• Je výstupní uzel prázdný?
• Je jeden uzel podmnožinou druhého.

U obvodů, které používají všechny štítky, jsou všechny tyto problémy ekvivalentní.

Důkaz

První problém je redukovatelný na druhý tím, že vezmeme průsečík výstupní brány a n. Ve skutečnosti bude nový výstup get prázdný právě tehdy n nebyl prvkem bývalé výstupní brány.

První problém je redukovatelný na třetí tím, že se zeptáte, zda je uzel n je podmnožina výstupního uzlu.

Druhý problém je redukovatelný na první, stačí vynásobit výstupní bránu číslem 0, pak 0 bude ve výstupní bráně právě tehdy, pokud původní výstupní brána nebyla prázdná.

Třetí problém je redukovatelný na druhý, kontrola, zda A je podmnožinou B, je ekvivalentní k otázce, zda je v ${ displaystyle A cap { overline {B}}}$.

Omezení

Nechť O je podmnožinou {∪, ∩, -, +, ×}, pak nazýváme MC (O) problém zjistit, zda je přirozené číslo uvnitř výstupní brány obvodu, jehož štítky bran jsou v O a MF (O) stejný problém s přidaným omezením, že obvod musí být a strom.

Rychle rostoucí sada

Jedna obtíž pochází ze skutečnosti, že doplněk konečné množiny je nekonečný a počítač má pouze konečnou paměť. Ale i bez doplňování lze vytvořit dvojitý exponenciál čísla. Nechat ${ displaystyle E_ {0} = {2 }, E_ {i + 1} = E_ {i} krát E_ {i}}$, pak lze snadno dokázat indukcí ${ displaystyle i}$ že ${ displaystyle E_ {i} = {2 ^ {2 ^ {i}} }}$, Vskutku ${ displaystyle E_ {0} = {2 } = {2 ^ {1} } = {2 ^ {2 ^ {0}} }}$ a indukcí ${ displaystyle E_ {i + 1} = E_ {i} krát E_ {i} = {2 ^ {2 ^ {i}} } krát {2 ^ {2 ^ {i}} } = {(2 ^ {2 ^ {i}}) ^ {2} } = {2 ^ {2 ^ {i} krát 2} } = {2 ^ {2 ^ {i + 1}} }}$.

A dokonce i dvojnásobné množiny exponenciálních velikostí: let ${ displaystyle S_ {0} = {0,1,2 }, S_ {i + 1} = (S_ {i} krát S_ {i}) + S_ {i}}$, pak ${ displaystyle {x | 0$, tj. ${ displaystyle S_ {i}}$ obsahuje ${ displaystyle 2 ^ {2 ^ {i}}}$ první číslo. To lze znovu dokázat indukcí dne ${ displaystyle i}$, platí pro ${ displaystyle S_ {0}}$ podle definice a nech ${ displaystyle x in {x | 0$, dělení ${ displaystyle x}$ podle ${ displaystyle 2 ^ {2 ^ {i}}}$ vidíme, že to lze zapsat jako ${ displaystyle x = 2 ^ {2 ^ {i}} krát d + r}$ kde ${ displaystyle d, r <2 ^ {2 ^ {i}}}$a indukcí, ${ displaystyle 2 ^ {2 ^ {i}}, d}$ a ${ displaystyle r}$ jsou v ${ displaystyle S_ {i}}$, opravdu ${ displaystyle x in (S_ {i} krát S_ {i}) + S_ {i}}$.

Tyto příklady vysvětlují, proč sčítání a násobení stačí k vytvoření problémů s vysokou složitostí.

Výsledky složitosti

Problém s členstvím

Problém s členstvím se ptá, zda, vzhledem k prvku n a obvod, n je ve výstupní bráně obvodu.

Když je třída autorizovaných bran omezena, problém s členstvím spočívá ve známých třídách složitosti. Všimněte si, že zde je proměnná size velikost obvodu nebo stromu; hodnota n se předpokládá, že je opraveno.

Problém ekvivalence

Problém ekvivalence se ptá, zda vzhledem k dvěma branám obvodu vyhodnotí stejnou sadu.

Když je omezena třída autorizovaných bran, problém ekvivalence spočívá uvnitř dobře známých tříd složitosti.^[1] EC (O) a EF (O) nazýváme problém ekvivalence obvodů a vzorců, jejichž brány jsou v O.

Reference

• Travers, Stephen (2006), „Složitost problémů s členstvím u obvodů přes množiny přirozených čísel“, Theoretical Computer Science: The Journal of the European Association for Theoretical Computer Science, Teoretická informatika, 389 (1): 211–229, doi:10.1016 / j.tcs.2006.08.017, ISSN  0304-3975

• Pierre McKenzie; Klaus W. Wagner (2003), „Složitost problémů s členstvím u obvodů přes množiny přirozených čísel“, Přednášky z informatiky, Springer-Verlag, 2607: 571–582, doi:10.1007/3-540-36494-3_50, ISBN  3-540-00623-0

• Breunig, Hans-Georg (2007), Složitost problémů s členstvím u obvodů nad množinami kladných čísel, FCT'07 Sborník z 16. mezinárodní konference o Základy teorie výpočtu, Springer-Verlag, s. 125–136, ISBN  978-3-540-74239-5

externí odkazy

• Pierre McKenzie, Složitost vyhodnocení obvodu nad přirozenými čísly