اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدHilberts Tenth problem and NP-completeness of Boolean Syllogistic with unordered cartesian product
160
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We relate the decidability problem for BS with unordered cartesian product with Hilberts Tenth problem and prove that BS with unordered cartesian product is NP-complete.
قيم البحث
اقرأ أيضاً
We solve the decidability problem for Boolean Set Theory with unordered cartesian product.
We formulate a property $P$ on a class of relations on the natural numbers, and formulate a general theorem on $P$, from which we get as corollaries the insolvability of Hilberts tenth problem, Godels incompleteness theorem, and Turings halting probl
em. By slightly strengthening the property $P$, we get Tarskis definability theorem, namely that truth is not first order definable. The property $P$ together with a Cantors diagonalization process emphasizes that all the above theorems are a variation on a theme, that of self reference and diagonalization combined. We relate our results to self referential paradoxes, including a formalisation of the Liar paradox, and fixed point theorems. We also discuss the property $P$ for arbitrary rings. We give a survey on Hilberts tenth problem for quadratic rings and for the rationals pointing the way to ongoing research in main stream mathematics involving recursion theory, definability in model theory, algebraic geometry and number theory.
The synchronization process of two mutually delayed coupled deterministic chaotic maps is demonstrated both analytically and numerically. The synchronization is preserved when the mutually transmitted signal is concealed by two commutative private fi
lters that are placed on each end of the communication channel. We demonstrate that when the transmitted signal is a convolution of the truncated time delayed output signals or some powers of the delayed output signals synchronization is still maintained. The task of a passive attacker is mapped onto Hilberts tenth problem, solving a set of nonlinear Diophantine equations, which was proven to be in the class of NP-Complete problems. This bridge between two different disciplines, synchronization in nonlinear dynamical processes and the realm of the NPC problems, opens a horizon for a new type of secure public-channel protocols.
We study a delay-sensitive information flow problem where a source streams information to a sink over a directed graph G(V,E) at a fixed rate R possibly using multiple paths to minimize the maximum end-to-end delay, denoted as the Min-Max-Delay probl
em. Transmission over an edge incurs a constant delay within the capacity. We prove that Min-Max-Delay is weakly NP-complete, and demonstrate that it becomes strongly NP-complete if we require integer flow solution. We propose an optimal pseudo-polynomial time algorithm for Min-Max-Delay, with time complexity O(log (Nd_{max}) (N^5d_{max}^{2.5})(log R+N^2d_{max}log(N^2d_{max}))), where N = max{|V|,|E|} and d_{max} is the maximum edge delay. Besides, we show that the integrality gap, which is defined as the ratio of the maximum delay of an optimal integer flow to the maximum delay of an optimal fractional flow, could be arbitrarily large.
We give a sufficient condition for Kripke completeness of modal logics enriched with the transitive closure modality. More precisely, we show that if a logic admits what we call definable filtration (ADF), then such an expansion of the logic is compl
ete; in addition, has the finite model property, and again ADF. This argument can be iterated, and as an application we obtain the finite model property for PDL-like expansions of logics that ADF.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
