Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHilberts Tenth problem and NP-completeness of Boolean Syllogistic with unordered cartesian product
160
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 problem. 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 filters 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 problem. 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 complete; 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
