Součet radikálů - Sum of radicals

v teorie výpočetní složitosti, existuje otevřený problém, zda některé informace o a součet radikálů lze vypočítat v polynomiální čas v závislosti na velikosti vstupu, tj. v počtu bitů nezbytných k vyjádření tohoto součtu. Je to důležité pro mnoho problémů v výpočetní geometrie, protože výpočet Euklidovská vzdálenost mezi dvěma body v obecném případě zahrnuje výpočet a odmocnina, a proto obvod a polygon nebo délka polygonálního řetězce má formu součtu radikálů.^[1]

Součet radikálů je definován jako konečný lineární kombinace radikálů:

{ displaystyle sum _ {i = 1} ^ {n} k_ {i} { sqrt [{r_ {i}}] {x_ {i}}},}

kde ${ displaystyle n, r_ {i}}$ jsou přirozená čísla a ${ displaystyle k_ {i}, x_ {i}}$ jsou reálná čísla.

Nej teoretičtější výzkum v výpočetní geometrie kombinatorického charakteru předpokládá výpočetní model nekonečné přesné skutečné RAM, tj. an abstraktní počítač ve kterém jsou reálná čísla a operace na nich prováděny s nekonečnou přesností a vstupní velikost reálného čísla a cena základní operace jsou konstanty.^[2] Nicméně, tam je výzkum v oblasti výpočetní složitosti, zejména v počítačová algebra, kde vstupní velikost čísla je počet bitů nezbytných pro jeho reprezentaci.^[3]

Obzvláště zajímavý ve výpočetní geometrii je problém stanovení podepsat součtu radikálů. Například délku polygonální cesty, ve které mají všechny vrcholy celé souřadnice, lze vyjádřit pomocí Pythagorova věta jako součet celých odmocnin, takže za účelem určení, zda je jedna cesta delší nebo kratší než jiná v a Euklidovská nejkratší cesta problém, je nutné určit znaménko výrazu, ve kterém je délka první cesty odečtena od druhé; tento výraz je součtem radikálů.

Podobným způsobem je problémem součet radikálů triangulace s minimální hmotností v Euklidovská metrika.

V roce 1991 Blömer navrhl polynomiální čas Algoritmus Monte Carlo pro určení zda je součet radikálů nula, nebo obecněji, zda představuje racionální číslo.^[4] I když Blömerův výsledek nevyřeší výpočetní složitost nalezení znaménka součtu radikálů, znamená to, že pokud je druhý problém v třída NP, pak je také v co-NP.^[4]

Viz také

Reference

^ Wolfgang Mulzer, Günter Rote, „Triangulace s minimální hmotností je tvrdá“, In: Sborník 22. Výroční sympozium o výpočetní geometrii, Sedona, 5. – 7. Června 2006, Deník ACM, Sv. 55, č. 2, 2008.
^ Franco P. Preparata a Michael Ian Shamos (1985). Výpočetní geometrie - úvod. Springer-Verlag. ISBN 978-0-387-96131-6. 1. vydání: 2. tisk, opraveno a rozšířeno, 1988:; Ruský překlad, 1989.
^ Příručka počítačové algebry, 2003, ISBN 3-540-65466-6
^ ^A ^b Blömer, Johannes (1991). Msgstr "Výpočet součtů radikálů v polynomiálním čase". [1991] Sborník 32. výroční sympozium základů informatiky. str. 670–677. doi:10.1109 / SFCS.1991.185434. ISBN 978-0-8186-2445-2..

[mulzer-1] Wolfgang Mulzer, Günter Rote, „Triangulace s minimální hmotností je tvrdá“, In: Sborník 22. Výroční sympozium o výpočetní geometrii, Sedona, 5. – 7. Června 2006, Deník ACM, Sv. 55, č. 2, 2008.

[2] Franco P. Preparata a Michael Ian Shamos (1985). Výpočetní geometrie - úvod. Springer-Verlag. ISBN 978-0-387-96131-6. 1. vydání: 2. tisk, opraveno a rozšířeno, 1988:; Ruský překlad, 1989.

[3] Příručka počítačové algebry, 2003, ISBN 3-540-65466-6

[blomer-4] A ^b Blömer, Johannes (1991). Msgstr "Výpočet součtů radikálů v polynomiálním čase". [1991] Sborník 32. výroční sympozium základů informatiky. str. 670–677. doi:10.1109 / SFCS.1991.185434. ISBN 978-0-8186-2445-2..

[1]

[2]

[3]

[4]