Comlexity and algebra  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
67870
Type K
Principal investigator Szabó, Csaba
Title in Hungarian Bonyolultságelmélet és algebra
Title in English Comlexity and algebra
Keywords in Hungarian Azonosság, P, NP, Részbenrendezett halmaz, CSP, Fundamentális csoport
Keywords in English Identity, Poset, P, NP, Unification, Fundamental Group
Discipline
Mathematics (Council of Physical Sciences)100 %
Panel Mathematics and Computing Science
Department or equivalent Department of Algebra and Number Theory (Eötvös Loránd University)
Participants Horváth, Gábor
Kátai-Urbán, Kamilla
Kun, Gábor
Pongrácz, András
Vértesi, Vera
Starting date 2007-07-01
Closing date 2011-07-31
Funding (in million HUF) 13.200
FTE (full time equivalent) 13.84
state closed project
Summary in Hungarian
A mai kutatásokban egyre nagyobb szerep jut a számítógépeknek. A matematika területén ez elsősorban számolások, számítások elvégzését illetve ellenőrzését jelenti. Kutatásainkban az algebrában felmerülő valamint az algebrai módszerekkel megfogható számítási problémák bonyolultságát vizsgáljuk. Az általános algebra legérdekesebb problémái az egyenlet megoldhatóság és az azonosságellenőrzés. E két probléma bonyolultságát vizsgáljuk, elsősorban a klasszikus algebrai struktúrákra (csoport, gyűrű, félcsoport) összpontosítva. Algebrai módszerekkel elemezzük a reláció homomorfizmus problémát. (CSP), ami a gráf- retrakciós probléma általánosítása. Vizsgálatainkban algebrai, topologikus és kombinatorikus módszereket használunk.
Summary
Nowadays, computers play larger and larger role in scientific research. It is especially true in mathematics where you often want to proceed calculations or computations with a machine. In our project we examine the interaction of algebra and computer science. On one hand we analyze the complexity of general algebraic questions, such as checking identies or solving equations over finite algebras. We concentrate on classical structures: groups, rings semigroups. On the other hand we investigate to the computational complexity of the famed CSP problem with general algebraic technics. We use algebraic, topological and combinatorial methods.




 

Final report

  
Results in Hungarian
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.
Results in English
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.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=67870
Decision
Yes





 

List of publications

  
Horváth EK; Horváth G; Németh Z; Szabó Cs: The number of square islands on a rectangular sea, Acta Sci. Math. (Szeged), 76, 35-48., 2010
Horváth EK; Németh Z; Pluhár G: The number of triangular islands on a triangular grid, Periodica Math. Hungar., 58, 25-34, 2009
Horváth G: Véges csoportok azonosságai, Matematikai Lapok, Új sorozat, 13 (2006/07) No. 2, 12-19, 2008
Horváth G: Functions and Polynomials over Finite Groups from the Computational Perspective, University of Hertfordshire, Hatfield, Egyesült Királyság, 2008
Horváth G: Bonyolultságelméleti problémák algebrai struktúrákban, ELTE Doktori Iskola, 2010
Horváth G.: The complexity of the equivalence and equation solvability problems over nilpotent rings and groups, Algebra Universalis, közlésre elfogadva, 2011
Horváth G;: The complexity of the equivalence problem over finite rings, Glasgow. Math. Journal, beküldve, 2010
Horváth G; Kátai-Urbán K; Pach PP; Pluhár G; Pongrácz A; Szabó Cs: The number of monounary algebras, Algebra Universalis, közlésre elfogadva, 2010
Horváth G; Kátai-Urbán K; Pach PP; Pluhár G; Pongrácz A; Szabó Cs: On free algebras in varieties generated by iterated semidirect products of semilattices, Int. J. Alg. Comput., közlésre elfogadva, 2011
Horváth G; Lawrence J; Mérai L; Szabó Cs: The Complexity of the Equivalence Problem for Nonsolvable Groups, Bulletin of the London Mathematical Society, 39 No. 3, 433-438, 2007
Horváth G; Mayr P; Pongrácz A: Characterizing translations on groups by cosets of their subgroups, Communications in Algebra, közlésre elfogadva, 2011
Horváth G; Mérai L: Szóprobléma nem feloldható csoportok fölött, Matematikai Lapok, Új sorozat, 13 (2006/07) No. 2, 20-27, 2008
Horváth G; Molnár-Sáska I: A mérgezett csokoládé rejtélye, Matematikai Lapok, Új sorozat, 13 (2006/07) No. 2, 28-43, 2008
Horváth G; Nehaniv CL; Szabó Cs: An assertion concerning functionally complete algebras and NP-completeness, Theoretical Computer Science, 407, 591-595, 2008
Horváth G; Szabó Cs: Equivalence and equation solvability problems for the group A_4, J. Pure Appl. Algebra, közlésre elfogadva, 2010
Horváth G; Szabó Cs: The extended equivalence and equation solvability problems over finite groups, Discrete Mathematics & Theoretical Computer Science, special issue at the occasion of László Babai's 60th birthday. közlésre elfogadva, 2010
Juhász ML; Pongrácz A: Embedding semilattices of subspaces of vector spaces, Studia Sci. Math. Hun., 48 No 1, 122-129., 2011
Kátai K: Kombinatorikus teljesen 0-egyszerű félcsoportok és szabad spektrum, SZTE, Doktori Iskola, 2009
Kátai-Urbán K, Pach PP, Pluhár G, Pongrácz A, Szabó Cs: On the word problem for syntactic monoids of piecewise testable languages, Semigroup Forum beküldve, 2011
Kátai-Urbán K; Szabó Cs: The pn sequence of semigroup varieties generatedby combinatorial 0-simple semigroups, Algebra Universalis, 59, 435–446, 2008
Kun G: Constraints, MMSNP and expander relational structures, Combinatorica, közlésre elfogadva, 2009
Kun G; Larose B: Maximal stable sets in analogs of Kneser and complete graphs, European Journal of Combinatorics, 30 No 1. 17-29., 2009
Kun G; Nesetril J: NP for Combinatorialists, EUROCOMB07, Electronic Notes in Discrete Mathematics, 29, 389-396, 2007
Kun G; Nesetril J: NP by means of lifts and shadows, MFCS 2007, 171-181, 2007
Kun G; Nesetril J: Forbidden lifts (NP and CSP for combinatorialists), European Journal of Combinatorics, 29 No. 4, 930-945, 2008
Kun G; O'Donnel R; Zhou Y: LP, width one and robust approximation of CSP's, kézirat, 2011
Kun G; Szegedy M: A new line attack on the dichotomy conjecture, STOC’09, 725-734, 2009
Kun G; Szegedy M: A new line of attack on the dichotomy conjecture, ECCC, 45 oldal, 2009
Kun G; Tardif C: Homomorphisms of random paths, European Journal of Combinatorics, 31 No. 3, 688-693, 2010
Lengvárszky Zs; Pach PP: A Note on Systems of Rectangular Islands: The Continuous Case, Acta Sci. Math. (szeged), 77 No 1-2, 37-44, 2011
Pach, PP: The Ramsey-type version of a problem of Pomerance and Schinzel, Acta Arithmetica, közlésre elfogadva, 2011
Pach PP; Pluhár G; Pongrácz A; Szabó Cs: The possible number of islands on the sea, Journal of Mathematical Analysis and Applications, 375 No 1, 8-13,, 2011
Pach, PP; Pluhár G; Pongrácz A; Szabó Cs: The number of trees of given depth, Electron. J. Combin., beküldve, 2011
Pach PP; Szabó Cs: On the minimal distance of near-ring codes, Discrete Mathematics and Theoretical Computer Science special issue, közlésre elfogadva, 2010
Pluhár G: Szavak száma idempotens félcsoportokban, Matematikai Lapok, Új sorozat, 13 (2006/07) No. 2, 44-53, 2008
Pluhár G: The number of brick islands by means of distributive lattices, Acta. Sci. Math. (Szeged), 75, 3-11, 2009
Pluhár G; Szabó Cs: The free spectrum of the variety of bands, Semigroup Forum, 76, 576-578, 2008
Pluhár G; Wood J: The free spectra of varieties generated by idempotent semigroups, Algebra and Discerete Mathematics, 2, 89 – 100, 2008
Stipsicz A; Vértesi V: On invariants for Legendrian knots, Pacific J. Math., 239, No. 1, 157--177., 2009
Szabó, Cs; Vértesi, V: The equivalence problem over finite rings, Int. J. Alg. Comput, 21 No. 3, 449-457, 2011
Vértesi V: Legendrian and transverse knots in the light of Heegaard Floer Homology, ELTE, doktori iskola, 2009
Vértesi V: Transversely nonsimple knots, Algebr. Geom. Topol., 8 No. 3, 1481--1498., 2009
Vértesi V; Plescheva S: Azonosságok 0-egyszerű félcsoportokban, Matematikai Lapok, Új sorozat, 13 (2006/07) No. 2, 54-75, 2008




 

Events of the project

  
2009-01-19 14:12:44
Résztvevők változása



Back »