https://m2.mtmt.hu/ hun 2026-05-02 10:23 PublicationOther 34202958 APPROVED true 0 false 2026-02-16T22:46:17.960+0000 2023-10-17T11:46:05.032+0000 2023-10-17T11:45:57.215+0000 true 10015168 Szakonyi Erzsebet /api/admin/10015168 Admin Szakonyi Erzsebet (RAMKI admin 4) true 10015168 2023-10-17T11:46:05.056+0000 2023-10-17T11:46:05.056+0000 Admin 10014568 /api/admin/10014568 Vándor Andrea (VA, admin) Vándor Andrea true 10014568 true 2024-04-18T08:02:54.796+0000 true true 29 29 /api/publicationtype/29 PublicationType Egyéb 15 true 29 PublicationOther true 10000361 Publication in repository true 29 29 /api/publicationtype/29 PublicationType Egyéb 15 true 29 PublicationOther /api/subtype/10000361 Csak repozitóriumban hozzáférhető közlemény SubType Csak repozitóriumban hozzáférhető közlemény (Egyéb) 1582 true 10000361 true 1 /api/category/1 Category Tudományos true 1 Tamás, Kátay 2023 We study Constraint Satisfaction Problems (CSPs) in an infinite context. We show that the dichotomy between easy and hard problems -- established already in the finite case -- presents itself as the strength of the corresponding De Bruijin-Erdős-type compactness theorem over ZF. More precisely, if D is a structure, let KD stand for the following statement: for every structure X if every finite substructure of X admits a solution to D, then so does X. We prove that if D admits no cyclic polymorphism, and thus it is NP-complete by the CSP Dichotomy Theorem, then KD is equivalent to the Boolean Prime Ideal Theorem (BPI) over ZF. Conversely, we also show that if D admits a cyclic polymorphism, and thus it is in P, then KD is strictly weaker than BPI. 2023 true false false false NONE 2026-02-16 false 2 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 2 0 0 0 0 0 Folyóiratcikk Journal Article 24 0 Könyvrészlet Chapter in Book 25 0 Könyv Book 23 0 Egyéb konferenciaközlemény Conference paper 31 0 Egyéb konferenciakötet Conference proceedings 32 0 Oltalmi formák Protection forms 26 0 Disszertáció Thesis 28 0 Egyéb Miscellaneous 29 2 Alkotás Achievement 22 0 Kutatási adat Research data 33 0 Folyóiratcikk Journal Article 24 0 0 0 Könyvrészlet Chapter in Book 25 0 0 0 Könyv Book 23 0 0 0 Egyéb konferenciaközlemény Conference paper 31 0 0 0 Egyéb konferenciakötet Conference proceedings 32 0 0 0 Oltalmi formák Protection forms 26 0 0 0 Disszertáció Thesis 28 0 0 0 Egyéb Miscellaneous 29 0 0 0 Alkotás Achievement 22 0 0 0 Kutatási adat Research data 33 0 0 0 2025 0 2 2 2 2 false 10076734 false false false 2024-01-15T12:46:04.815+0000 Analízis Tanszék (ELTE / TTK / Mat_I); Csoportok és gráfok - Lendület (HRN RAMKI); Matematika Doktori Iskola (ELTE / TTK) 3 11 3 3 0 false 10014568 Language 10002 /api/language/10002 Angol Angol English true 2 true PersonAuthorship 110591758 /api/authorship/110591758 Tamás, Kátay [Kátay, Tamás (Matematika), szerző] Matematika Doktori Iskola (ELTE / TTK) 1 0.33333334 true false Author 10082322 /api/author/10082322 Kátay Tamás (Matematika) Kátay Tamás true true Tamás Kátay true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PersonAuthorship 110591759 /api/authorship/110591759 László, Márton Tóth [Tóth, László Márton (csoportelmélet), szerző] Csoportok és gráfok - Lendület (HRN RAMKI) 2 0.33333334 false false Author 10076734 /api/author/10076734 Tóth László Márton (csoportelmélet) Tóth László Márton true true László Márton Tóth true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PersonAuthorship 110591760 /api/authorship/110591760 Zoltán, Vidnyánszky [Vidnyánszky, Zoltán (Matematika), szerző] Analízis Tanszék (ELTE / TTK / Mat_I) 3 0.33333334 false true Author 10044975 /api/author/10044975 Vidnyánszky Zoltán (Matematika) Vidnyánszky Zoltán true 10044975 true Zoltán Vidnyánszky true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PublicationIdentifier 24534247 /api/publicationidentifier/24534247 arXiv: 2310.00514 PlainSource 37 /api/publicationsource/37 arXiv PublicationSourceType 10007 /api/publicationsourcetype/10007 Repozitórium true true true arXiv http://arxiv.org/abs/@@@ true true 37 true 2310.00514 http://arxiv.org/abs/2310.00514 false true Classification 10004 /api/classification/10004 Elméleti és alkalmazott matematika true true Classification 10005 /api/classification/10005 Logika és alapvetés true true Classification 10019 /api/classification/10019 Számítástudományi matematika true true /api/publication/34202958 Tamás Kátay et al. The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms. (2023)<div class="PublicationOther Publication long-list"> <div class="authors"> <img title="Forrásközlemény" style="float: left" src="/frontend/resources/grid/publication-core-icon.png"> <div class="autype autype0"> <span class="author-name" mtid="10082322"><a href="/gui2/?type=authors&mode=browse&sel=10082322" target="_blank">Tamás Kátay (<span class="authorship-author-name">Kátay Tamás</span> <span class="authorAux-mtmt"> Matematika</span>) </a> </span> <span class="author-affil"><span title="Eötvös Loránd Tudományegyetem">ELTE</span>/<span title="Természettudományi Kar">TTK</span>/Matematika Doktori Iskola</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10076734"><a href="/gui2/?type=authors&mode=browse&sel=10076734" target="_blank">László Márton Tóth (<span class="authorship-author-name">Tóth László Márton</span> <span class="authorAux-mtmt"> csoportelmélet</span>) </a> </span> <span class="author-affil"><span title="Rényi Alfréd Matematikai Kutatóintézet">RAMKI</span>/Csoportok és gráfok - Lendület</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10044975"><a href="/gui2/?type=authors&mode=browse&sel=10044975" target="_blank">Zoltán Vidnyánszky (<span class="authorship-author-name">Vidnyánszky Zoltán</span> <span class="authorAux-mtmt"> Matematika</span>) </a> </span> <span class="author-affil"><span title="Eötvös Loránd Tudományegyetem">ELTE</span>/<span title="Természettudományi Kar">TTK</span>/<span title="Matematikai Intézet">Mat_I</span>/Analízis Tanszék</span> </div> </div> <div class="title"><a href="/gui2/?mode=browse&params=publication;34202958" target="_blank">The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms</a></div> <div class="description"> </div> <div class="country"> Megjelenés: <span class="publishedYear">(2023)</span> </div> <div class="pub-footer"> <span class="language" xmlns="http://www.w3.org/1999/html">Nyelv: Angol | </span> <span class="identifiers"> <span class="id identifier oa_none" title="none"> <a style="color:black" title="2310.00514" target="_blank" href="http://arxiv.org/abs/2310.00514"> arXiv </a> </span> </span> <div class="publication-citation" style="margin-left: 0.5cm;"> <span title="Nyilvános idézőközlemények összesen, említések nélkül" class="citingPub-count">Nyilvános idéző összesen: 2</span> | Független: 2 | Függő: 0 | Nem jelölt: 0 </div> <div class="mtid"><span class="long-pub-mtid">Közlemény: 34202958</span> | <span class="status-data status-APPROVED"> Nyilvános </span> Forrás | <span class="type-subtype">Egyéb ( Csak repozitóriumban hozzáférhető közlemény ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData">kézi felvitel</span> </div> <div class="lastModified">Utolsó módosítás: 2023.10.17. 13:46 Szakonyi Erzsebet (RAMKI admin 4) </div> <div class="lockedBy">Központi kezelésű 2024.04.18. 10:02 Vándor Andrea (VA, admin) </div> </div></div>