Bonyolultságelmélet és algebra = Complexity and algebra

Szabó, Csaba and Horváth, Gábor and Kátai-Urbán, Kamilla and Kun, Gábor and Pongrácz, András and Vértesi, Vera (2012) Bonyolultságelmélet és algebra = Complexity and algebra. Project Report. OTKA.

Preview

PDF 67870_ZJ1.pdf Download (327kB) | Preview

Abstract

Az elmúlt négy évben számos, a CSP-vel kapcsolatos problémát vizsgáltunk. 43 tudományos dolgozatot publikáltunk, ezek nagy részét vezető nemzetközi folyóiratokban. Legfontosabb eredményeink a következők: A Feder-Vardi tételt általánosítva beláttuk, hogy a CSP problémák osztálya polinomiálisan ekvivalens a Monotone Monadic Strict NP osztállyal. Igazoltuk, hogy a lineáris programmal approximálható CSP problémák osztálya pontosan az 1-szélességű osztály. Bebizonyítottuk, hogy függvényteljes algebrákra az ekvivalenciaprobléma bonyolultsága coNP-teljes. Továbbá beláttuk, hogy kommutatív gyűrűk felett a szigma ekvivalencia probléma P-beli, ha pedig a gyűrű Jacobson-radikál szerinti faktora nemkommutatív, akkor coNP-teljes. Kezdeményeztük a kiterjesztett egyenletmegoldhatóság és ekvivalencia vizsgálatát, és beláttuk a kapcsolódó dichotómiatételeket csoportokra. | In the last four years we studied several problems concerning CSP. We published 43 research papers, mainly in leading international journals. Our most important results are the following: We generalized the Feder-Vardi Theorem by proving that every Monotone Monadic Strict NP problem is polynomially equivalent to a CSP problem. We showed that the class of CSP problems that can be approximated by a linear program coincides with the class of problems of width one. We proved that the equivalence problem is coNP-complete for functionally complete algebras. We showed that the sigma equivalence problem can be solved in polynomial time for commutative rings and is coNP-complete if the factor by the Jacobson radical is not commutative. We introduced the extended equivalence and equation solvability problems and we proved the corresponding dichotomy theorems for groups.

Actions (login required)

Edit Item