Egyenletmegoldhatóság bonyolultsága néhány véges csoport felett
Loading...
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
DOI
Abstract
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 speciális mátrixcsoportokra 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.