تقرير
GMSNP and Finite Structures
| العنوان: | GMSNP and Finite Structures |
|---|---|
| المؤلفون: | Guzmán-Pro, Santiago |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Mathematics - Combinatorics, Mathematics - Logic, 05C15, 03B70, 05C63, F.4.2, G.2.2 |
| الوصف: | Given an (infinite) relational structure $\mathbb S$, we say that a finite structure $\mathbb C$ is a minimal finite factor of $\mathbb S$ if for every finite structure $\mathbb A$ there is a homomorphism $\mathbb S\to \mathbb A$ if and only if there is a homomorphism $\mathbb{C} \to \mathbb{A}$. In this brief note we prove that if CSP($\mathbb S$) is in GMSNP, then $\mathbb S$ has a minimal finite factor $\mathbb C$, and moreover, CSP($\mathbb C$) reduces in polynomial time to CSP($\mathbb S$). We discuss two nice applications of this result. First, we see that if a finite promise constraint satisfaction problem PCSP($\mathbb A,\mathbb B$) has a tractable GMSNP sandwich, then it has a tractable finite sandwich. We also show that if $\mathbb G$ is a non-bipartite (possibly infinite) graph with finite chromatic number, and CSP($\mathbb G$) is in GMSNP, then CSP($\mathbb G$) in NP-complete, partially answering a question recently asked by Bodirsky and Guzm\'an-Pro. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2406.13529 |
| رقم الأكسشن: | edsarx.2406.13529 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |