đ-categorical structures avoiding height 1 identities
Notice bibliographique
Résumé
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and is NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each nontrivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega"> <mml:semantics> <mml:mi> Ï </mml:mi> <mml:annotation encoding="application/x-tex">\omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction distillée sur la base complÚte
Imitation des enseignantsNi prĂ©valence calibrĂ©e, ni vĂ©ritĂ© terrain. Validation humaine Ă venir. Apprise Ă partir de 10 348 Ă©tiquettes directes de Codex et de 10 348 Ă©tiquettes directes de Gemma. Le mode candidate est l'union des tĂȘtes enseignantes seuillĂ©es; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des Ă©tiquettes humaines ni des Ă©tiquettes directes de modĂšles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| MĂ©tarecherche | 0,000 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,001 |
| Ătudes des sciences et des technologies | 0,000 | 0,000 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,001 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modÚle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Les deux tĂȘtes enseignantes du modĂšle Ă©tudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catĂ©gorie, et le statut de validation accompagne chaque rangĂ©e tel quel.
Scores de référence d'un modÚle non mature (critÚres de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validĂ©ePrĂ©diction automatique; un appel candidat dâune seule tĂȘte enseignante, pas un consensus.
Le détail, modÚle par modÚle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».