Egyenletmegoldhatóság bonyolultsága egy 54 elemű csoport felett

Dátum
2011-11-17T13:49:46Z
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt

A dolgozatban az egyenletmegoldhatóság, illetve ekvivalencia problémák bonyolultságát vizsgáltuk véges csoportok felett. Korábbi eredmények szerint nilpotens csoportok felett ezen döntési problémák P-beliek. Továbbá ismert, hogy nem feloldható csoportok felett az egyenletmegoldhatóság NP-teljes, az ekvivalencia coNP-teljes. Feloldható, nem nilpotens csoportok között, eddig csak néhány meta-Abel csoportra volt ismert ezen problémák bonyolultsága. A dolgozatban egy olyan 54- elemű csoportra határoztuk meg az egyenletmegoldhatóság, illetve ekvivalencia bonyolultságát, amelyre ezek eddig még nem voltak ismertek. Igazoltuk, hogy ezen csoport feletti egyenletmegoldhatóság, illetve ekvivalencia problémák polinom időben eldönthetőek.

Leírás
Kulcsszavak
bonyolultság, csoport, egyenletmegoldhatóság
Forrás