Ugrás a tartalomhoz

Rejtettrészcsoport-probléma

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

A rejtettrészcsoport-probléma a következő: ha adva van egy csoport és egy függvény, ami a csoport egy részcsoportjának mellékosztályain különböző konstans értékeket vesz fel, meghatározható-e a részcsoport az elemszámához képest polinomiális időben? Számos fontos matematikai probléma megfogalmazható a rejtettrészcsoport-probléma speciális eseteként, például a prímfaktorizáció vagy a gráfizomorfizmus.

A rejtett részcsoport probléma fontos kutatási terület a kvantuminformatikában, mert egyes fajtáinál kvantumalgoritmussal a leghatékonyabb ismert algoritmushoz képest exponenciális gyorsulást lehet elérni. Legismertebb esete ennek a Shor-algoritmus.