Algebrai módszerek a bonyolultságelméletben  részletek

súgó  nyomtatás 
vissza »
 

Projekt adatai

  
azonosító
109185
típus K
Vezető kutató Horváth Gábor
magyar cím Algebrai módszerek a bonyolultságelméletben
Angol cím Algebraic methods in computational complexity
magyar kulcsszavak algebra, bonyolultság, homogenitás, szóprobléma
angol kulcsszavak algebra, complexity, homogenity, word problem
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Algebra
zsűri Matematika–Számítástudomány
Kutatóhely TTK Algebra és Számelmélet Tanszék (Debreceni Egyetem)
résztvevők Kátai-Urbán Kamilla
Pongrácz András
Szabó Csaba
projekt kezdete 2013-09-01
projekt vége 2018-03-31
aktuális összeg (MFt) 10.920
FTE (kutatóév egyenérték) 6.90
állapot lezárult projekt
magyar összefoglaló
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A pályázat az algebra, a modellelmélet és a bonyolultságelmélet kölcsönhatásait vizsgálja.

Célunk az ekvivalencia, egyenletmegoldhatóság és straight line program különböző változatainak bonyolultságának meghatározása. Különösen a gyűrűk feletti szigma problémákat, a csoportok feletti kiterjesztett problémákat (elsősorban a kommutátorral való kiegészítést), valamint a félcsoportok feletti problémákat tartjuk érdekesnek. Össze kívánjuk hasonlítani különböző számítási modellek hatékonyságát, különös hangsúlyt fektetve az alternáló csoportokra épülő automatákra.

Félcsoportok körében a varietások szabad spektrumának meghatározása egyre nagyobb népszerűségnek örvend. Elsősorban Seif sejtését vizsgálnánk, melyben már jelentős előrelépést tettünk félhálók iterált szemidirekt szorzatának vizsgálatával. Továbbá szeretnénk a J-triviális monoiddal felismerhető, k-darabonként tesztelhető nyelvek szavaira normál formát adni.

A modellelmélet vonatkozásában Thomas egy sejtését próbáljuk igazolni konkrét struktúrákra illetve speciális esetekben. A generikus részbenrendezés illetve a Henson-gráfokból konstansjel hozzáadásával kapott struktúrák reduktjainak elsőrendű átdefiniálhatóság erejéig való karakterizálása nagy érdeklődésre tart számot. A részbenrendezés reduktjait primitív pozitív átdefiniálhatóság erejéig is vizsgáljuk, ami elméleti számítástudományban elvezethet a dichotómiatétel bizonyításához a CSP-k egy részosztályára. Konkrét konstrukciókat keresünk a legfontosabb homogén struktúrákra, illetve kezdeményezzük ezek bonyolultságelméleti vizsgálatát.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
- Az ekvivalencia, egyenletmegoldhatóság és straight line program különböző változatai bonyolultságának meghatározása.

- Gyűrűk feletti szigma problémák bonyolultságának meghatározása.

- Csoportok feletti kommutátorral való kiterjesztett ekvivalencia és egyenlegmegoldhatóság bonyolultságának meghatározása.

- Félcsoportok feletti ekvivalencia, egyenletmegoldhatóság és straight line program bonyolultságának meghatározása.

- Seif sejtés: egy véges monoid szabad spektruma pontosan akkor nem dupla exponenciális, ha a monoid idempotensei által generált félcsoportban nincs nemtriviális részcsoport.

- 4-darabonként tesztelhető nyelvek szavaihoz normál forma meghatározása.

- Különböző számítási modellek hatékonyságának összehasonlítása.

- Boole algebrára épülő számítási modell és alternáló csoportra épülő véges automata hatékonyságának összehasonlítása.

- Thomas sejtés: minden véges nyelv feletti homogén relációstruktúrának véges sok reduktja van elsőrendű átdefiniálhatóság erejéig.

- Karakterizáljuk a generikus poset és a Henson-gráfokból konstans hozzáadásával kapott struktúrák reduktjait elsőrendű átdefiniálhatóság erejéig. Ez igazolná Thomas sejtését ezen struktúrákra.

- Megvizsgáljuk a generikus részbenrendezés reduktjait primitív pozitív átdefiniálhatóság erejéig, ezzel igazoljuk a dichotómiatételt a CSP-k megfelelő részosztályára.

- Adjunk konkrét konstrukciót a generikus részbenrendezésre.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A tervezett kutatás három különböző matematikai tudományág, az algebra, a modellelmélet és a bonyolultságelmélet határterületén zajlik. Így az eredmények is több matematikai terület gyarapodását eredményezhetik.

A bonyolultságelméletben felmerülő kérdéseknek (mint például az ekvivalencia vagy az egyenletmegoldhatóság különböző változatai) rendre vannak gyakorlati alkalmazásai: a polinomidőben megoldható problémák gyors algoritmust, az NP-teljes problémák nehezen feltöhető kódolási lehetőséget nyújtanak. Az egyenletmegoldhatóság mindezeken felül az unifikációelméletben, a normál formák a formális nyelvek elméletében játszanak fontos szerepet.

A különböző dichotómia eredmények új szemléletet nyújthatnak az algebrában is. Ez történt például a véges csoportok szabad spektrumának klasszifikációjával. Bízunk abban, hogy a félcsoportok szabad spektrumára vonatkozó kutatásunk is hasonló befolyással lesz a jövő félcsoportelméleti struktúratételeire.

Az alapvető számítási modellek vizsgálata hosszú távon magában hordozza a gyakorlati felhasználás lehetőségét. Természetesen rövidtávon is eredményes összehasonlítani a különböző modellek hatékonyságát, hogy megtudjuk, melyik problémát melyik számítási modellben érdemes vizsgálni/megoldani.

Végül, a homogén struktúrák témakörben elért bármely eredmény a modellelméletet (közelebb kerülni a Thomas sejtés bizonyításához) és az elméleti számítástudományt (végtelen célstruktúrájú CSP-k visszavezetése véges célstruktúrájúakra) is előbbre viszi. Hosszú távú célunk, hogy olyan modellelméleti módszereket dolgozzunk ki, melyek mindkét tudományterületen alkalmazhatóak és további kapcsolatot teremtsenek közöttük.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Az utóbbi két é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áljuk. Elsősorban általános és klasszikus algebrai módszereket igénylő kérdésekkel foglalkozunk.

Ilyen például az általános algebra egyik legérdekesebb problémája, az egyenlet megoldhatóság. E probléma bonyolultságát vizsgáljuk véges klasszikus algebrai struktúrákra (csoport, gyűrű, félcsoport) összpontosítva. Algebrai módszerekkel elemezzük különböző számítási modellek hatékonyságát, mint a kiterjesztett ekvivalencia vagy a straight line program. Egy másik kérdés végtelen homogén struktúrák (pl: véletlen gráf) és azok retraktjainak algoritmikus leírása és vizsgálata. Főleg a véges típusú tulajdonságokkal -- mint egyelemű kiterjesztés vagy automorfizmus kiterjesztésének lokális jellemzése -- foglalkozunk. Ezek a kutatások az online- és véletlen algoritmusok elméletében játszanak fontos szerepet.
angol összefoglaló
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
In our research project we examine the interaction of algebra, model theory and computer science.

We plan to determine the complexity of the usual, sigma, extended and straight line versions of the equivalence and equation solvability problems over various classical algebraic structures (rings, groups, semigroups).
In particular we are interested in analyzing the sigma problems over rings, the extended problems over groups when we extend by the commutator, and any of these problems over semigroups.
We plan to compare the efficiency of alternative models of computations.
We start by examining the different models based on a finite, simple, non-Abelian group, specifically on an alternating group.

Investigation into the free spectra of semigroup varieties is of greater and greater interest.
We intend to confirm Seif's conjecture. We already made a significant step by verifying it for iterated semidirect products of semilattices.
Moreover, we aim to develop normal forms for the k-piecewise testable languages, recognized by J-trivial monoids.

In model theory we plan to examine Thomas' famous conjecture by verifying it for test structures and special cases.
We are particularly interested in the reducts of the generic partial order and the reducts of the Henson graphs with a constant up to first-order interdefinability.
We study the reducts of the generic partial order up to primitive positive interdefinability in order to obtain a dichotomy theorem for a subclass of CSP's in theoretical computer science.
We give transparent presentations for the most important homogeneous structures, and initiate the concept of complexity of these presentations.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
- Determine the complexity of the various versions of the equivalence, equation solvability and straight line problems.

- Determine the complexity of the sigma problems for rings.

- Determine the complexity of the extended problems for groups when the group is extended by the commutator.

- Determine the complexity of the equivalence, equation solvability and straight line problems over semigroups.

- Seif's conjecture: The free spectra of finite monoid is not doubly exponential if and only if the semigroup generated by the idempotents of the monoid contains no nontrivial subgroups.

- Determine normal forms for 4-piecewise testable languages.

- Compare the efficiency of alternative models of computations.

- Compare models of computations based on the two-element Boolean algebra to finite state machines based on an alternating group.

- Thomas' Conjecture: Every homogeneous structure over a finite relational language has finitely many reducts up to first-order interdefinability.

- Characterize the reducts of the generic poset and of the Henson graphs with a constant up to first-order interdefinability, and thus verify Thomas' conjecture for these structures.

- Study the reducts of the generic poset up to primitive positive interdefinability, and verify the dichotomy theorem for the corresponding subclass of CSP's.

- Give a short presentation to the generic poset.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
The proposed research consists of mathematical questions in the borderline of Algebra, Model Theory and Computer Science. Therefore, the results of the research can affect several different areas of Mathematics and Computer Science.

Computational complexity questions (like the various versions of equivalence and equation solvability problems) tend to have a direct impact on applied mathematics by obtaining programmable algorithms for problems of polynomial time complexity or possible cryptographic applications for NP-complete problems. Moreover, equation solvability has great relevance in unification theory, and so do normal forms in the theory of formal languages.

Algebra would benefit as well, as different dichotomy theorems could yield to a deeper understanding on the properties of various algebraic structures. This was indeed the case e.g. with the dichotomy theorem for the free spectra of groups. We expect our results concerning combinatorics on words over finite semigroups to similarly influence the strucure theorems of semigroups in the future.

New foundations of computations always have the potential of a long term industrial application. Nevertheless, comparing different computational models could reveal which models are more appropriate tackling certain specific computational problems.

Last but not least, any accomplishment concerning homogeneous structures could improve model theory (by investigating Thomas' conjecture) and theoretical computer science (by reducing infinite domain constraint satisfaction problems to finite domain ones).
Our long-term goal is to develop model theoretic methods that improve upon both areas simultaniously, and reveal further connections between Model Theory and Computer Science.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Recently algebraic methods play larger and larger role in algorithmic-, computational- and complexity questions. In our proposal we examine the interaction of algebra, model theory and computer science. Among others we analyze the complexity of general algebraic questions, such as solving equations over finite algebras, primarily for classical structures: groups, rings, semigroups. We investigate the problems for several models of computations, such as the extended problems or straight line programming.

Another problem we consider is the investigation of the finitary properties of infinite homogeneous structures and their retracts from computational aspects. The main goal is to define the computational complexity of local properties of these structures, and describe them for different presentations. Such analysis would play an important role in the theory of random algorithms and in online programming.




 

Zárójelentés

  
kutatási eredmények (magyarul)
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.
kutatási eredmények (angolul)
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.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=109185
döntés eredménye
igen





 

Közleményjegyzék

  
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




 

Projekt eseményei

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



vissza »