Sciencemag.cz
Doporučujeme
Jako subset sum se označuje úloha, kdy je na jedné straně zadána množina přirozených čísel, na druhé straně (větší) přirozené číslo. Ptáme se, zda v množině existuje podmnožina, jejíž součet dává dané číslo. Úloha patří do kategorie NP úplných problémů, to znamená, že s velikostí zadání (součtu i prvků podmnožiny) roste čas potřebný k výpočtu exponenciálně; přesněji řečeno, NP (nedeterministicky polynomiální) úplné problémy znamenají, že není znám žádný algoritmus s polynomiální složitostí a v polynomiální čase lze pouze ověřit, zda již známé řešení úlohy je správné. Známým typem NP úplných problémů je např. problém obchodního cestujícího nebo problém splnitelnosti (satisfiability).
Poznámky PH:
NP úplné úlohy jsou na sebe vzájemně převoditelné.
Pro NP úplné úlohy není aktuálně znám žádný efektivní kvantový algoritmus.
Faktorizace není NP úplný problém (nebo to alespoň nikdo nedokázal a předpokládá se, že patří do výpočetně méně náročné třídy; efektivnější kvantový algoritmus pro faktorizaci tedy NP úplné problémy neřeší).
Otázka, jaký je vztah mezi NP a P, patří mezi 7 největších problémů matematiky pro 21. století, jejichž řešení ocenil Clayův matematický ústav částkou milionu dolarů. Většinou se očekává, že nakonec někdo dokáže, že NP se nerovná P. Opak by byl velkým překvapením. (To už se jaka druhé nejpravděpodobnější možnost spíš někdy předpokládá, že úloha je nerozhodnutelná.)
Popularizátor matematiky Keith Devlin (Problémy pro třetí tisíciletí, Argo a Dokořán 2005) mimochodem uvedl, že problém P vs. NP by eventuálně (jako jediný z oněch 7) mohl vyřešit i nějaký amatér, nikoliv profesionální matematik.
Výzkumníci z několika čínských institucí nyní přišli s tím, že sub set problém by mohl dobře zvládat i optický (fotonický) počítač. Konkrétní zadání problému bylo zakódováno přímo do hardwaru. Pomocí femtosekundového laseru vyleptali vědci zadání do skla v podobě sítě 3D vlnovodů. Fotony se pak v této síti rozptýlí a procházejí stavový prostor, tj. hledají – paralelně – řešení úlohy, „kontrolují všechny kombinace součtů najednou“. Ukázalo se, že fotonický počítač pro danou úlohu pracuje efektivněji než klasický superpočítač a s růstem velikosti úlohy je také lépe škálovatelný (tj. díky paralelismu čím složitější úloha, tím větší má fotonický počítač výhodu proti klasickému a méně ho ohrožuje kombinatorická exploze).
Jde spíš o demonstraci. Pro průmyslové nasazení by bylo určitě třeba, aby skleněná struktura byla univerzální a její konfigurace na konkrétní problém se prováděla jednoduše změnou nastavení/softwarově. Jinak celý princip poněkud připomíná DNA počítače, které také nabízely oproti klasických počítačům masivní paralelismus (molekuly zkoušejí vedle sebe všechny kombinace současně), ale do praxe se neprosadily.
Xiao-Yun Xu et al. A scalable photonic computer solving the subset sum problem, Science Advances (2020). DOI: 10.1126/sciadv.aay5853
Zdroj: Science Advances/Phys.org a další
