REAL

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.

[img]
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.

Item Type: Monograph (Project Report)
Uncontrolled Keywords: Matematika
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: Kotegelt Import
Date Deposited: 01 May 2014 05:59
Last Modified: 31 Jul 2014 12:21
URI: http://real.mtak.hu/id/eprint/11889

Actions (login required)

Edit Item Edit Item