O složitosti problému G-rekonstrukce

Abstrakt

Zkoumáme výpočetní složitost třídy rozhodovacích problémů nazývaných G-rekonstrukce. Dokazujeme, že tyto problémy jsou NP-úplné pro mnoho hodnot parametru G.

Klíčová slova

• complexity
• G-reconstruction
• problem