Algebraic methods in computational complexity  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
109185
Type K
Principal investigator Horváth, Gábor
Title in Hungarian Algebrai módszerek a bonyolultságelméletben
Title in English Algebraic methods in computational complexity
Keywords in Hungarian algebra, bonyolultság, homogenitás, szóprobléma
Keywords in English algebra, complexity, homogenity, word problem
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Algebra
Panel Mathematics and Computing Science
Department or equivalent Department of Algebra and Number Theory (University of Debrecen)
Participants Kátai-Urbán, Kamilla
Pongrácz, András
Szabó, Csaba
Starting date 2013-09-01
Closing date 2018-03-31
Funding (in million HUF) 10.920
FTE (full time equivalent) 7.36
state running project





 

Final report

 
Results in Hungarian
Az utóbbi néhány évtizedben egyre nagyobb szerep jut az algebrai módszereknek algoritmikus-, bonyolultságelméleti- és számítástudományi kérdésekben. Kutatásainkban az algebrában és modellelméletben felmerülõ, valamint az algebrai módszerekkel megfogható számítási problémákat és e problémák bonyolultságelméleti megközelítését vizsgáltuk. Elsõsorban általános és klasszikus algebrai módszereket igénylõ kérdésekkel foglalkoztunk. Ilyen például az algebra egyik legrégebbi problémája, az egyenletek megoldhatósága. Újabb csoportosztályok felett sikerült eldöntenünk ennek a problémának a bonyolultságát, és az eddig ismert esetekben is minden eddiginél hatékonyabb eljárást adtunk a probléma eldöntésére. Továbbá klasszikus véges struktúrák (gyűrű, csoport) feletti polinomok szerkezetét ismertük meg jobban, sokszor algoritmikus szemszögből is. Némely eredményünkre akár egy teljesen új típusú számítási modellt is lehet építeni. A végtelen homogén struktúrák (pl. véletlen részbenrendezett halmaz) és reduktjaik szerkezetének feltárásában elért eredményeink kiegészítik és új megvilágításba helyezik a korábbi tételeket és sejtéseket. Ennek a területnek a számítástudományban a kielégíthetőség probléma bonyolultságának eldöntésében van fontos szerepe, melyet véges esetben nemrég zártak le. Az egyik cikkben egy olyan új témát vezettünk be, mely ezen probléma végtelen változatának lezárásához nyújthat alapvető eszközt.
Results in English
Recently algebraic methods play larger and larger role in algorithmic-, computational- and complexity questions. We investigated the interaction of algebra, model theory and computer science. Among others we analyzed the complexity of general algebraic questions, such as solving equations over finite algebras, primarily for classical structures: groups, rings. We have determined the complexity of this question for new classes of groups, and for all the previously known cases we have provided much faster algorithms than the existing ones. We have analyzed the structure of polynomials over rings and groups, in many cases even from an algorithmic perspective. Some of our results lay down completely new foundations for computation. Another problem we considered was the investigation of the finitary properties of infinite homogeneous structures (e.g. random poset) and their reducts from computational aspects. Our results extend the previous theorems and conjectures, and put some of them into a new context. These results play an important role in the infinite version of the constraint satisfaction problem. This problem has just been solved recently in the finite case. We have initiated a new topic, which may provide the key ingredient in handling the infinite case.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=109185
Decision
Yes





 

List of publications

 
Pach P P, Pinsker M, Pluhár G, Pongrácz A, Szabó Cs: Reducts of the random partial order, ADV MATH 267: 94-120, 2014
Grasegger G, Horváth G, Kearnes K A: Polynomial Equivalence of Finite Rings, J AUST MATH SOC 96: (2) 244-257, 2014
Földvári A: The complexity of the equation solvability problem over semipattern groups, beküldve, 2016
Bodor B, Kalina K, Szabó Cs: Functional reducts of Boolean algebras, INT J ALGEBRA COMPUT, to appear, 2016
Bodor B, Kalina K, Szabó Cs: Permutation groups containing infinite linear groups and reducts of infinite dimensional linear spaces over the two element field, COMMUN ALGEBRA 45: (7), 2942–2955, 2017
Árendás P, Blázsik L Z, Bodor B, Szabó Cs: On the complexity and topology of scoring games: of Pirates and Treasure, INTEGERS: Electronic Journal Of Combinatorial Number Theory 17, G3, 2017
Horváth G, Nehaniv C L, Podoski K: The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs, INT J ALGEBRA COMPUT, to appear, 2017
Bodirsky M, Bradley-Williams D, Pinsker M, Pongrácz A: The universal homogeneous binary tree, submitted, 2016
Bodirsky M, Martin B, Pinsker M, Pongrácz A: Constraint satisfaction problems for reducts of homogeneous graphs, submitted, 2016
Martin B, Pongrácz A, Wrona M: The complexity of counting quantifiers on equality languages, THEOR COMPUT SCI 670: 56-67, 2017
Földvári A: The complexity of the equation solvability problem over semipattern groups, INT J ALGEBRA COMPUT 27: (2), 259-272, 2017
Bodirsky M, Pinkser M, Pongrácz A: Projective clone homomorphisms, Journal of Symbolic Logic, to appear, 2017
Kátai-Urbán K, Pongrácz A, Szabó Cs: The fine- and generative spectra of varieties of monounary algebras, submitted, 2017
Pongrácz A: Discordant voting for the knights of the round table, submitted, 2017
Cameron P, Bodor, B Szabó Cs: Infnitely many reducts of homogeneous structures, submitted, 2017
Földvári A: The complexity of the equation solvability problem over nilpotent groups, INT J ALGEBRA COMPUT, to appear, 2017
Bulyovszky B, Horváth G: Polynomial functions over finite commutative rings, THEOR COMPUT SCI, to appear, 2017
Görcsös D, Horváth G, Mészáros A: Permutation polynomials over finite rings, submitted, 2017
Bodirsky M, Martin B, Pinsker M, Pongrácz A: Constraint satisfaction problems for reducts of homogeneous graphs, submitted, 2016
Földvári A: The complexity of the equation solvability problem over semipattern groups, INT J ALGEBRA COMPUT 27: (2), 259-272, 2017
Balázs Bulyovszky, Gábor Horváth: Polynomial functions over finite commutative rings, THEOR COMPUT SCI 703: pp. 76-86., 2017
Gábor Horváth, Chrystopher L Nehaniv, Károly Podoski: The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs, INT J ALGEBR COMPUT 27: (7) pp. 863-886., 2017
Nehaniv C L, Rhodes J L, Egri-Nagy A, Dini P, Rothstein Morris E, Horváth G, Karimi F, Schreckling D, Schilstra M J: Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions, PHILOS TRANS - R SOC A 373: (2046) 46, 2015
Árendás P, Blázsik L Z, Bodor B, Szabó Cs: On the complexity and topology of scoring games: of Pirates and Treasure, beküldve, 2015
Bodor B, Kalina K: A projektív tér reduktjai, Matematikai Lapok 20: (2) 14-19, 2014
Bodirsky M, Pinkser M, Pongrácz A: Projective clone homomorphisms, J SYMBOLIC LOGIC, to appear, 2017
Bodor B, Kalina K: Az $F_2^\infty$ vektortér reduktjai, Matematikai Lapok 20: (2) 20-28, 2014
Bodor B, Kalina K: Az $F_p^\omega$ vektortér reduktjai páratlan prímek esetén, Matematikai Lapok 20: (2) 29-56, 2014
Bodor B, Kalina K: Boole-algebrák funkcionális reduktjai, Matematikai Lapok 20: (2) 57-72, 2014
Bodor B, Kalina K, Szabó Cs: Functional reducts of Boolean algebras, International Journal of Algebra and Computation, feltételesen elfogadva, 2016
Bodor B, Kalina K, Szabó Cs: Permutation groups containing infinite linear groups and reducts of infinite dimensional linear spaces over the two element field, Communications in Algebra, elfogadva, 2016
Árendás P, Bencs F, Blázsik L Z, Kalina K, Szabó Cs: Compositions of complements of graphs, INTEGERS: Electronic Journal Of Combinatorial Number Theory 16, A29, 2016
Árendás P, Blázsik L Z, Bodor B, Szabó Cs: On the complexity and topology of scoring games: of Pirates and Treasure, beküldve, 2016
Horváth G, Nehaniv C L, Podoski K: The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs, beküldve, 2016
Bodirsky M, Bradley-Williams D, Pinsker M, Pongrácz A: The universal homogeneous binary tree, beküldve, 2016
Bodirsky M, Martin B, Pinsker M, Pongrácz A: Constraint satisfaction problems for reducts of homogeneous graphs, beküldve, 2016
Martin B, Pongrácz A, Wrona M: The complexity of counting quantifiers on equality languages, beküldve, 2016
Horváth G, Székelyhidi L, Wilkens B: Non-synthesizable varieties, J MATH ANAL APPL 417: (1) 394-399, 2014
Bodor B, Kalina K, Szabó Cs: Functional reducts of Boolean algebras, beküldve, 2014
Pach P P, Pinsker M, Pluhár G, Pongrácz A, Szabó Cs: Reducts of the random partial order, ADV MATH 267, pp. 94–120, 2014
Bodor B, Kalina K, Szabó Cs: Permutation groups containing the infinite linear groups and reducts of infinite dimensional linear spaces over the two element field, beküldve, 2014
Bodor B, Kalina K, Szabó Cs: Compositions of complements of graphs, beküldve, 2014
Horváth G, Nehaniv C L: Length of polynomials over finite groups, J. COMPUT. SYSTEM SCI., elfogadva, 2014
Horváth G: The complexity of the equivalence and equation solvability problems over meta-Abelian groups, beküldve, 2014
Grasegger G, Horváth G, Kearnes K A: Polynomial Equivalence of Finite Rings, J AUST MATH SOC 96: (2) 244-257, 2014
Bodor B, Kalina K, Szabó Cs: Functional reducts of Boolean algebras, beküldve, 2015
Bodor B, Kalina K, Szabó Cs: Permutation groups containing infinite linear groups and reducts of infinite dimensional linear spaces over the two element field, beküldve, 2015
Árendás P, Bencs F, Blázsik L Z, Kalina K, Szabó Cs: Compositions of complements of graphs, beküldve, 2015
Horváth G: The complexity of the equivalence and equation solvability problems over meta-Abelian groups, J ALGEBRA 433: 208-230, 2015
Horváth G, Nehaniv C L: Length of polynomials over finite groups, J COMPUT SYST SCI 81: (8) 1614-1622, 2015
Kátai-Urbán K, Pongrácz A, Szabó Cs: The fine- and generative spectra of varieties of monounary algebras, submitted, 2017
Pongrácz A: Discordant voting for the knights of the round table, submitted, 2017
Bodirsky M, Bradley-Williams D, Pinsker M, Pongrácz A: The universal homogeneous binary tree, J LOGIC COMPUT 28: (1), 133-163, 2018
Földvári A: The complexity of the equation solvability problem over nilpotent groups, J ALGEBRA 495, 289-303, 2018
Dalma Görcsös, Gábor Horváth, Anett Mészáros: Permutation polynomials over finite rings, FINITE FIELDS TH APP 49: pp. 198-211., 2018
Cameron P, Bodor, B Szabó Cs: Infnitely many reducts of homogeneous structures, ALGEBRA UNIVERSALIS, to appear, 2018
Bodor B, Kalina K, Szabó Cs: Functional reducts of Boolean algebras, INT J ALGEBRA COMPUT, to appear, 2018
Kátai-Urbán K, Pongrácz A, Szabó Cs: Voting protocols on the star graph, submitted, 2018
Földvári A, Horváth G: The complexity of the equation solvability and equivalence problems over finite groups, submitted, 2018





 

Events of the project

 
2016-01-05 09:34:21
Résztvevők változása




Back »