Let G=(V,E) be a simple graph. A function f : V -> {-1, +1} is said to be a reverse signed dominating function if the sum of its function values over any closed neighborhood is at most zero. The reverse signed domi...
详细信息
ISBN:
(纸本)9783642340406
Let G=(V,E) be a simple graph. A function f : V -> {-1, +1} is said to be a reverse signed dominating function if the sum of its function values over any closed neighborhood is at most zero. The reverse signed domination number of a graph G equals the maximum weight of a reverse signed dominating function of G. In this paper, we show that the decision problem corresponding to the problem of computing the reverse signed domination number is NP-complete. Furthermore, We present a linear time algorithm for finding a maximal reverse signed dominating function in an arbitrary tree.
Growing interest in providing and improving radio coverage for mobile phones and wireless LANs inside buildings has recently emerged. The need of such coverage appears mainly in office buildings, shopping malls in ver...
详细信息
ISBN:
(纸本)9781424447534
Growing interest in providing and improving radio coverage for mobile phones and wireless LANs inside buildings has recently emerged. The need of such coverage appears mainly in office buildings, shopping malls in very complex environment. Although the three dimensional FDTD method has shown great promise, the calculation time is very environment dependent and exceeds the calculation time of ray tracing or ray launching in most cases. In this article, we focus on the theoretical estimation and comparison of FDTD and ray methods in aspects of the algorithmic complexity.
Kolmogorov-Chaitin complexity has long been believed to be impossible to approximate when it comes to short sequences (e.g. of length 5-50). However, with the newly developed coding theorem method the complexity of st...
详细信息
Kolmogorov-Chaitin complexity has long been believed to be impossible to approximate when it comes to short sequences (e.g. of length 5-50). However, with the newly developed coding theorem method the complexity of strings of length 2-11 can now be numerically estimated. We present the theoretical basis of algorithmic complexity for short strings (ACSS) and describe an R-package providing functions based on ACSS that will cover psychologists' needs and improve upon previous methods in three ways: (1) ACSS is now available not only for binary strings, but for strings based on up to 9 different symbols, (2) ACSS no longer requires time-consuming computing, and (3) a new approach based on ACSS gives access to an estimation of the complexity of strings of any length. Finally, three illustrative examples show how these tools can be applied to psychology.
A covert channel is a communication channel that bypasses the access controls of the system, and it is a threat to the system's security. In this paper, we propose a new covert timing channel which exploits the al...
详细信息
ISBN:
(纸本)9781612842325
A covert channel is a communication channel that bypasses the access controls of the system, and it is a threat to the system's security. In this paper, we propose a new covert timing channel which exploits the algorithmic complexity vulnerabilities in the name lookup algorithm of the kernel. This covert channel has a high capacity and it is practically exploitable. In our experiments, the data rate reaches 2256 bps under a very low error rate. This data rate is high enough for practical use. So our covert channel is dangerous. To our knowledge, no previous works propose this covert channel nor implement it. We describe our design and implementation of the covert channel on a SELinux system, discuss the subtle issues that arose in the design, present performance data of the covert channel and analyse its capacity.
Counterfactuals have become an important area of interdisciplinary interest, especially in logic, philosophy of language, epistemology, metaphysics, psychology, decision theory, and even artificial intelligence. In th...
详细信息
Counterfactuals have become an important area of interdisciplinary interest, especially in logic, philosophy of language, epistemology, metaphysics, psychology, decision theory, and even artificial intelligence. In this study, we propose a new form of analysis for counterfactuals: analysis by algorithmic complexity. Inspired by Lewis-Stalnaker's Possible Worlds Semantics, the proposed method allows for a new interpretation of the debate between David Lewis and Robert Stalnaker regarding the Limit and Singularity assumptions. Besides other results, we offer a new way to answer the problems raised by Goodman and Quine regarding vagueness, context-dependence, and the non-monotonicity of counterfactuals. Engaging in a dialogue with literature, this study will seek to bring new insights and tools to this debate. We hope our method of analysis can make counterfactuals more understandable in an intuitively plausible way, and a philosophically justifiable manner, aligned with the way we usually think about counterfactual propositions and our imaginative reasoning.
For a finite structure Mon the domain of k >= 2 elements consider the description of the Galois closures InvEnd(M) and InvAut(M) (the set of relations on the domain of M that are invariant to all endomorphisms, res...
详细信息
For a finite structure Mon the domain of k >= 2 elements consider the description of the Galois closures InvEnd(M) and InvAut(M) (the set of relations on the domain of M that are invariant to all endomorphisms, resp. automorphisms of M) via positive existential formulae over the signature of M. It is shown that for every relation R from the set InvEnd(M) (R from InvAut(M)) there exists a positive existential formula over M (resp., over M and the inequality predicate) with no more than (k-1)m (m is the size of R) existential quantifiers that defines R. This implies that every first order n-ary (n >= 1) predicate over M (i.e., with n free variables) is equivalent to a positive existential formula over M and inequality with at most (k-1)(kn-1) existential quantifiers and this estimate does not depend on the signature of M. Next, for a finite M with a finite signature there is a cubic algorithm that for every R on the domain of M it recognizes properties: R belongs to InvAut(M) (that is, R is defined by some first order predicate over M), as well as R belongs to InvEnd(M). Moreover, for such structure M there is a quadratic algorithm that for every R from InvAut(M) (R from InvEnd(M)) it produces a positive existential formula over the unnested atomic predicates from M and the inequality x not equal y (resp., over unnested atomic predicates from M), which defines R in mO(n2) steps, where n is the arity of R. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
In this paper, we study the EXACT SUBSET MULTICOVER problem (or ESM), which can be seen as an extension of the well-known SET COVER problem. Let (U , f) be a multiset built from set U = {e1, e2, ... , em} and function...
详细信息
In this paper, we study the EXACT SUBSET MULTICOVER problem (or ESM), which can be seen as an extension of the well-known SET COVER problem. Let (U , f) be a multiset built from set U = {e1, e2, ... , em} and function f : U- & Nopf;*. ESM is defined as follows: given (U, f) and a collection S = {S1, S2, ... , Sn} of n subsets of U , is it possible to find a multiset (S', g) with S' = {S'1, S2', ... , S' n } and g : S'- & Nopf;, such that (i) Si'c Si for every 1 <= i <= n, and (ii) each element of U appears as many times in (U , f) as in (S', g) ? We study this problem under an algorithmic viewpoint and provide diverse complexity results such as polynomial cases, NP- hardness proofs and FPT algorithms. We also study two variants of ESM: (i) EXCLUSIVE EXACT SUBSET MULTICOVER (EESM), which asks that each element of U appears in exactly one subset Si ' of S ';(ii) MAXIMUM EXCLUSIVE EXACT SUBSET MULTICOVER (MAX-EESM), an optimization version of EESM, which asks that a maximum number of elements of U appear in exactly one subset S i ' of S ' . For both variants, we provide several complexity results;in particular we present a 2-approximation algorithm for MAX-EESM, that we prove to be tight. For these three problems, we also provide an Integer Linear Programming (ILP) formulation.
A fast deblurring network, based on a high-performance convolutional network and pixel volume, is proposed to address the limitations of existing video deblurring algorithms, which often overly emphasize inter-frame i...
详细信息
A fast deblurring network, based on a high-performance convolutional network and pixel volume, is proposed to address the limitations of existing video deblurring algorithms, which often overly emphasize inter-frame information, leading to high algorithmic complexity. First, high-performance convolutional networks are utilized to prune the deblurring network, thereby reducing both the number of model parameters and computational complexity. To address the increased network computational complexity resulting from the extensive use of traditional two-dimensional convolutional layers, depthwise over-parameterized convolutions are employed to replace traditional convolutions. This substitution significantly reduces computational complexity without compromising the network's structure and performance. In addition, the Charbonnier loss function is used to approximate the mean absolute error (MAE) loss function to alleviate the over-smoothing problem. At the same time, the problem of non-differentiability of the MAE loss function at zero is solved by adding a constant, to enhance the visual quality of video images. Experimental results demonstrate that the proposed method delivers superior deblurring performance. Compared with the baseline pixel volume deblurring network framework, our method achieves a significant reduction in model complexity, demonstrating 28.73% fewer parameters and 59.96% lower floating-point operations, underscoring its theoretical significance. (c) 2025 SPIE and IS&T
This study explores fundamental aspects of probability theory within the framework of constructing random sequences random number generators. We propose an interpretation of probability spaces and operations on formal...
详细信息
This study explores fundamental aspects of probability theory within the framework of constructing random sequences random number generators. We propose an interpretation of probability spaces and operations on formal events the theory of formal languages, utilizing string manipulation techniques. As part of the research, we present implementation of the discussed concepts in the form of a program that generates random numbers of the required by processing signals from a sound card. Additionally, the problem of primality testing, which is particularly relevant practical cryptographic applications, is addressed. We critically examine common misconceptions regarding the properties Carmichael numbers and the application of Fermat's Little Theorem. Furthermore, we propose an efficient primality algorithm.
Let E c Rn be a union of line segments and F c Rn the set obtained from E by extending each line segment in E to a full line. Keleti's line segment extension conjecture posits that the Hausdorff dimension of F sho...
详细信息
Let E c Rn be a union of line segments and F c Rn the set obtained from E by extending each line segment in E to a full line. Keleti's line segment extension conjecture posits that the Hausdorff dimension of F should equal that of E. Working in R2, we use effective methods to prove a strong packing dimension variant of this conjecture. Furthermore, a key inequality in this proof readily entails the planar case of the generalized Kakeya conjecture for packing dimension. This is followed by several doubling estimates in higher dimensions and connections to related problems.
暂无评论