FINITE ALGEBRAS WITH HOM-SETS OF POLYNOMIAL SIZE

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10509210" target="_blank" >RIV/00216208:11320/25:10509210 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=GNN2aokBOE" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=GNN2aokBOE</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1090/tran/9262" target="_blank" >10.1090/tran/9262</a>

Jazyk výsledku

angličtina

Název v původním jazyce

FINITE ALGEBRAS WITH HOM-SETS OF POLYNOMIAL SIZE

Popis výsledku v původním jazyce

We provide an internal characterization of those finite algebras(i.e., algebraic structures) A such that the number of homomorphisms fromany finite algebra X to A is bounded from above by a polynomial in the sizeof X. Namely, an algebra A has this property if, and only if, no subalgebraof A has a nontrivial strongly abelian congruence. We also show that theproperty can be decided in polynomial time for algebras in finite signatures.Moreover, if A is such an algebra, the set of all homomorphisms from X to Acan be computed in polynomial time given X as input. As an application ofour results to the field of computational complexity, we characterize inherentlytractable constraint satisfaction problems over fixed finite structures, i.e., thosethat are tractable and remain tractable after expanding the fixed structure byarbitrary relations or functions.

Název v anglickém jazyce

FINITE ALGEBRAS WITH HOM-SETS OF POLYNOMIAL SIZE

Popis výsledku anglicky

We provide an internal characterization of those finite algebras(i.e., algebraic structures) A such that the number of homomorphisms fromany finite algebra X to A is bounded from above by a polynomial in the sizeof X. Namely, an algebra A has this property if, and only if, no subalgebraof A has a nontrivial strongly abelian congruence. We also show that theproperty can be decided in polynomial time for algebras in finite signatures.Moreover, if A is such an algebra, the set of all homomorphisms from X to Acan be computed in polynomial time given X as input. As an application ofour results to the field of computational complexity, we characterize inherentlytractable constraint satisfaction problems over fixed finite structures, i.e., thosethat are tractable and remain tractable after expanding the fixed structure byarbitrary relations or functions.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Transactions of the American Mathematical Society

ISSN

0002-9947

e-ISSN

1088-6850

Svazek periodika

378

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

28

Strana od-do

569-596

Kód UT WoS článku

001312730200001

EID výsledku v databázi Scopus

2-s2.0-85210412140