Polynomiální testování identity - Polynomial identity testing

V matematice polynomiální testování identity (PIT) je problém efektivního určení, zda dva vícerozměrné polynomy jsou identické. Více formálně je algoritmu PIT dána aritmetický obvod který počítá polynom p v a pole, a rozhodne, zda p je nulový polynom. Určení výpočetní složitost požadovaný pro testování polynomiální identity je jedním z nejdůležitějších otevřených problémů v algebraické výpočetní složitosti.

Popis

Otázka „Má ${displaystyle (x + y) (x-y)}$ rovnat se ${displaystyle x ^ {2} -y ^ {2} ,?}$"je otázka, zda jsou dva polynomy identické. Stejně jako u jakékoli testovací otázky polynomiální identity, lze ji triviálně transformovat na otázku" Je určitý polynom rovný 0? "; v tomto případě se můžeme zeptat" Má ${displaystyle (x + y) (x-y) - (x ^ {2} -y ^ {2}) = 0}$„? Pokud dostaneme polynom jako algebraický výraz (spíše než jako černou skříňku), můžeme potvrdit, že rovnost platí prostřednictvím násobení a sčítání hrubou silou, ale časová složitost přístupu brutální síly roste ${displaystyle {binom {n + d} {d}}}$, kde ${displaystyle n}$ je počet proměnných (zde ${displaystyle n = 2}$: ${displaystyle x}$ je první a ${displaystyle y}$ je druhý) a ${displaystyle d}$ je stupeň polynomu (zde, ${displaystyle d = 2}$). Li ${displaystyle n}$ a ${displaystyle d}$ jsou oba velké, ${displaystyle {binom {n + d} {d}}}$ roste exponenciálně.^[1]

PIT se týká toho, zda je polynom identický s nulovým polynomem, spíše než toho, zda se funkce implementovaná polynomem v dané doméně vždy vyhodnotí na nulu. Například pole se dvěma prvky, GF (2), obsahuje pouze prvky 0 a 1. V GF (2), ${displaystyle x ^ {2} -x}$ vždy se vyhodnotí na nulu; navzdory tomu PIT neuvažuje ${displaystyle x ^ {2} -x}$ být roven nulovému polynomu.^[2]

Stanovení výpočetní složitosti potřebné pro testování polynomiální identity je jedním z nejdůležitějších otevřených problémů v matematickém podpole známém jako „algebraická výpočetní složitost“.^[1][3] Studium PIT je stavebním kamenem mnoha dalších oblastí výpočetní složitosti, jako je například důkaz toho IP =PSPACE.^[1][4] Kromě toho má PIT aplikace pro Tutte matice a také testování primality, kde techniky PIT vedly k Test prvosti AKS, první deterministický (i když nepraktický) polynomiální čas algoritmus pro testování primality.^[1]

Formální prohlášení o problému

Vzhledem k aritmetický obvod který počítá a polynomiální v pole, určete, zda je polynom roven nulovému polynomu (tj. polynomu bez nenulových členů).^[1]

Řešení

V některých případech není specifikace aritmetického obvodu dána řešiči PIT a řešitel PIT může zadávat hodnoty pouze do „černé skříňky“, která obvod implementuje, a poté analyzovat výstup. Všimněte si, že níže uvedená řešení předpokládají, že jakákoli operace (například násobení) v daném poli trvá konstantní čas; dále všechny níže uvedené algoritmy černé skříňky předpokládají, že velikost pole je větší než stupeň polynomu.

The Schwartz – Zippel Algoritmus poskytuje praktické pravděpodobnostní řešení jednoduchým náhodným testováním vstupů a kontrolou, zda je výstup nulový. Bylo to první randomizovaný polynomiální čas Algoritmus PIT se ukázal jako správný.^[1] Čím větší je doména, ze které jsou vstupy čerpány, tím je méně pravděpodobné, že Schwartz – Zippel selže. Pokud je nedostatek náhodných bitů, vyžaduje algoritmus Chen-Kao (nad racionálními hodnotami) nebo Lewin-Vadhanův algoritmus (nad jakýmkoli polem) méně náhodných bitů za cenu více požadovaného běhu.^[2]

A řídký PIT má nanejvýš ${displaystyle m}$ nenulové monomiální podmínky. Řídký PIT lze deterministicky vyřešit v polynomiální čas velikosti obvodu a počtu ${displaystyle m}$ monomials,^[1] viz také.^[5]

A nízký stupeň PIT má horní hranici stupně polynomu. Jakýkoli problém PIT nízkého stupně lze snížit na subexponenciální čas velikosti obvodu do problému PIT pro obvody hloubky čtyři; proto je PIT pro obvody hloubky čtyři (a níže) intenzivně studován.^[1]

Viz také

• Aplikace lemmatu Schwartz – Zippel

externí odkazy

• Poznámky z přednášky o „Testování polynomiální identity pomocí lemmatu Schwartz-Zippel“
• Polynomiální testování identity od Michaela Forbese - MIT na Youtube
• Vítěz ceny za polynomiální testování identity

Reference