اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNetwork satisfaction for symmetric relation algebras with a flexible atom
101
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify the computational complexity of the network satisfaction problem for all finite relation algebras $bf A$. We provide a complete classification for the case that $bf A$ is symmetric and has a flexible atom; the problem is in this case NP-complete or in P. If a finite integral relation algebra has a flexible atom, then it has a normal representation $mathfrak{B}$. We can then study the computational complexity of the network satisfaction problem of ${bf A}$ using the universal-algebraic approach, via an analysis of the polymorphisms of $mathfrak{B}$. We also use a Ramsey-type result of Nev{s}etv{r}il and Rodl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.
قيم البحث
اقرأ أيضاً
We study some finite integral symmetric relation algebras whose forbidden cycles are all 2-cycles. These algebras arise from a finite field construction due to Comer. We consider conditions that allow other finite algebras to embed into these Comer a
lgebras, and as an application give the first known finite representation of relation algebra $34_{65}$, one of whose atoms is flexible. We conclude with some speculation about how the ideas presented here might contribute to a proof of the flexible atom conjecture.
This note introduces a generalization to the setting of infinite-time computation of the busy beaver problem from classical computability theory, and proves some results concerning the growth rate of an associated function. In our view, these results
indicate that the generalization is both natural and promising.
Finite-domain constraint satisfaction problems are either solvable by Datalog, or not even expressible in fixed-point logic with counting. The border between the two regimes coincides with an important dichotomy in universal algebra; in particular, t
he border can be described by a strong height-one Maltsev condition. For infinite-domain CSPs, the situation is more complicated even if the template structure of the CSP is model-theoretically tame. We prove that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (Q;<); such CSPs are called temporal CSPs and are of fundamental importance in infinite-domain constraint satisfaction. Our main result is a complete classification of temporal CSPs that can be expressed in one of the following logical formalisms: Datalog, fixed-point logic (with or without counting), or fixed-point logic with the Boolean rank operator. The classification shows that many of the equivalent conditions in the finite fail to capture expressibility in Datalog or fixed-point logic already for temporal CSPs.
For formulas F of propositional calculus I introduce a metavariable MF and show how it can be used to define an algorithm for testing satisfiability. MF is a formula which is true/false under all possible truth assignments iff F is satisfiable/unsati
sfiable. In this sense MF is a metavariable with the meaning F is SAT. For constructing MF a group of transformations of the basic variables ai is used which corresponds to flipping literals to their negation. The whole procedure corresponds to branching algorithms where a formula is split with respect to the truth values of its variables, one by one. Each branching step corresponds to an approximation to the metatheorem which doubles the chance to find a satisfying truth assignment but also doubles the length of the formulas to be tested, in principle. Simplifications arise by additional length reductions. I also discuss the notion of logical primes and show that each formula can be written as a uniquely defined product of such prime factors. Satisfying truth assignments can be found by determining the missing primes in the factorization of a formula.
The constraint satisfaction problem (CSP) of a first-order theory $T$ is the computational problem of deciding whether a given conjunction of atomic formulas is satisfiable in some model of $T$. We study the computational complexity of $mathrm{CSP}(T
_1 cup T_2)$ where $T_1$ and $T_2$ are theories with disjoint finite relational signatures. We prove that if $T_1$ and $T_2$ are the theories of temporal structures, i.e., structures where all relations have a first-order definition in $(mathbb{Q};<)$, then $mathrm{CSP}(T_1 cup T_2)$ is in P or NP-complete. To this end we prove a purely algebraic statement about the structure of the lattice of locally closed clones over the domain ${mathbb Q}$ that contain $mathrm{Aut}(mathbb{Q};<)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
