Narrow Results

This paper further explores the phase transitions of the EXPSPACE-complete problems, focusing on the conformant plan modification. By analyzing features of the conformant plan modification, quantitative results are obtained. If the number of actions is't greater than θ_ub, almost all the conformant planning instances can't be solved with the conformant plan modification. If the number of actions is't lower than θ_lb, almost all the conformant planning instances can be solved with the conformant plan modification. The results of the experiments show that there indeed exists an experimental threshold γ_c of density (ratio of number of actions to number of propositions), which separates the region where almost all conformant planning instances can't be solved with the conformant plan modification from the region where almost all conformant planning instances can be solved with the conformant plan modification.

The random (2 + p)-SAT model has been proposed [18] to study the possible relation between the “order” of phase transitions and computational complexity. It was also claimed that there exists p_c > 0, such that for p < p_c the random (2 + p)-SAT instance behaves like 2-SAT. Later, Achlioptas et al. [3] obtained the first rigorous results that 0.4 ≤ p_c ≤ 0.695, the methods they use are the first moment method and the simple Unit-Clause algorithm. In this paper, we try to optimize the local maximality condition of the truth assignments when implementing the first moment method. We prove that the phase transition point of clauses-to-variables ratio r (dependent on p) can be improved. Moreover, we show that the upper bound of p_c can be reduced to 0.6846. This fact implies that, for a constant λ < 1, a random (2 + p)-SAT formula with λn 2-clauses and 2.17n 3-clauses is almost surely unsatisfiable.

The counting exact satisfiablity problem (#XSAT) is a problem that computes the number of truth assignments satisfying only one literal in each clause. This paper presents an algorithm that solves the #XSAT problem in O(1.1995ⁿ), which is faster than the best algorithm running in O(1.2190ⁿ), where n denotes the number of variables. To increase the efficiency of the algorithm, a new principle, called common literals principle, is addressed to simplify formulae. This allows us to further eliminate literals. In addition, we firstly apply the resolution principles into solving #XSAT problem, and therefore it improves the efficiency of the algorithm further.

In this paper, we study bounds for optimal constant dimension codes further. By revising the construction for constant dimension codes in [4], we improve some bounds on q-ary constant dimension codes in some cases. By combinatorial method, we show that there exists no optimal constant dimension code A_q[n, 2δ, k] meeting both Wang-Xing-Safavi-Naini-Bound and the maximal distance separate bound simultaneously.

G. Bracha presented in 1987 a simple and efficient reliable broadcast algorithm for $n$-process asynchronous message-passing systems, which tolerates up to $t<n/3$ Byzantine processes. Following an idea recently introduced by Hirt, Kastrato and Liu-Zhang (OPODIS 2020), instead of considering the upper bound on the number of Byzantine processes $(t)$, the present short article considers two types of Byzantine behavior: the ones that can prevent the safety property from being satisfied, and the ones that can prevent the liveness property from being satisfied (a Byzantine process can exhibit only one or both types of failures). This Byzantine differentiated failure model is captured by two associated upper bounds denoted $t_s$ (for safety) and $t_{\ell }$ for liveness). The article shows that only the threshold values used in the predicates of Bracha’s algorithm must be modified to obtain an algorithm that works with this differentiated Byzantine failure model.

Most of us may have had the experience of forgetting some term from a physical book when the term appears in neither the table of contents nor the index. Unfortunately, we must search for it page by page. In one edition of the popular physical book “Harry Potter and the Sorcerer’s Stone”, for example, the term “dragon’s blood” only appears on pages 81 and 175, so browsing through the whole book to find it would be inevitable. In this study, a mechanism is provided to carry out an online search on physical books. To financially support this mechanism, we can put online advertisements with different offers on these physical books. An advertisement scheduling problem (ASP) is therefore formulated to maximize the total profit. To obtain the optimal schedules, we propose a branch-and-bound algorithm equipped with an upper bound. Experimental results show that the proposed upper bound performs well and completes the search in only 4% of the execution time of an ordinary branch-and-bound algorithm.

The upper bound U_B(t) of the time derivative of entropy for a dynamical system driven by both additive colored noise and multiplicative colored noise with colored cross-correlation is investigated. Based on the Fokker–Planck equation, the effects of the parameters on U_B(t) are analyzed. The results show that: (i) α (the multiplicative noise intensity), D (the additive noise intensity) and τ₂ (the correlation time of the additive noise) always enhance U_B (t) monotonically; (ii) λ (the intensity of the cross-correlation between the multiplicative noise and the additive noise), τ₁ (the correlation time of the multiplicative noise), τ₃ (the correlation time of the cross-correlation) and γ (the dissipative constant) all possess a minimum, i.e., U_B (t) decreases for small values and increases for large values.

In this paper we have studied information dynamics of both internal and external noises driven harmonic oscillator. Based on the Fokker–Planck description of the stochastic processes and the Schwarz inequality principle we have calculated upper bound of rate of change of information entropy with time and its deviation from the time derivative of the entropy. The bound and the deviation monotonically decreases to zero during the relaxation of a given nonequilibrium state to a stationery state. The relaxation time increase with increase of noise correlation time of the internal colored thermal noise but it is independent on the correlation time of the external colored noise. However, an extremum behavior appears in the variation of the bound as a function of parameter of the system such as damping strength, noise correlation time of thermal and nonthermal noises etc.

Reconfiguring a very large scale integration (VLSI) array with faults is to construct a maximum logical sub-array (target array) without faults. A large target array implies a good harvest of the corresponding reconfiguration algorithm. Thus, a tight upper bound of the harvest can be directly used to evaluate the performance of the reconfiguration algorithm. This paper presents a new approach to calculate the upper bound of the harvest for the VLSI arrays with clustered faults. The latest upper bound is successfully reduced and the proposed technique to calculate the upper bound is bound into a reconfiguration algorithm cited in this paper. Simulation results show that the upper bound is reduced up to 20% on 256 × 256 array with clustered faults, and the corresponding reconfiguration process is significantly accelerated over 30%, without loss of harvest.

In this paper, we study the bound on the number of isolated zeros of Abelian integrals associated with the seventh-degree hyperbolic Hamiltonian system. When the unperturbed system has a unique period annulus bounded by a heteroclinic loop, a series of results on the upper bound of the number of zeros of the related Abelian integrals are obtained. However, there are still some open problems left about the exact bound. Furthermore, we give some results for the system when the parameters in the Hamiltonian system are fixed to certain values. The main tools involve algebraic symbolic computations such as counting the zeros of semi-algebraic systems.

For the quadratic reversible systems of genus one, all of their periodic orbits are higher-order algebraic curves. When they are perturbed by polynomials of degree $n$, the numbers of zeros of their Abelian integrals will change and we study the upper bounds of these numbers by using the methods of Riccati equation and Picard–Fuchs equation. We consider both the highest and lowest degrees of polynomials, and more importantly, we consider the law of polynomials and the range of values for their variables. Consequently, some laws of the polynomials are discovered and many upper bounds are obtained, and these upper bounds are sharper than the results obtained by other techniques.

In 1991, Negami found an upper bound on the stick number s(K) of a nontrivial knot K in terms of crossing number c(K) which is s(K) ≤ 2c(K). In this paper we give a new upper bound in terms of arc index, and improve Negami's upper bound to . Moreover if K is a nonalternating prime knot, then .

In this paper we use continued fractions to study a partial order on the set of 2-bridge knots derived from the work of Ohtsuki, Riley, and Sakuma. We establish necessary and sufficient conditions for any set of 2-bridge knots to have an upper bound with respect to the partial order. Moreover, given any 2-bridge knot K₁ we characterize all other 2-bridge knots K₂ such that {K₁, K₂} has an upper bound. As an application we answer a question of Suzuki, showing that there is no upper bound for the set consisting of the trefoil and figure-eight knots.

Lomonaco and Kauffman introduced a knot mosaic system to give a definition of a quantum knot system which can be viewed as a blueprint for the construction of an actual physical quantum system. A knot n-mosaic is an n × n matrix of 11 kinds of specific mosaic tiles representing a knot or a link by adjoining properly that is called suitably connected. D_n denotes the total number of all knot n-mosaics. Already known is that D₁ = 1, D₂ = 2 and D₃ = 22. In this paper we establish the lower and upper bounds on D_n

An equilateral stick number s₌(K) of a knot K is defined to be the minimal number of sticks required to construct a polygonal knot of K which consists of equal length sticks. Rawdon and Scharein [Upper bounds for equilateral stick numbers, in Physical Knots: Knotting, Linking, and Folding Geometric Objects in ℝ³, Contemporary Mathematics, Vol. 304 (American Mathematical Society, Providence, RI, 2002), pp. 55–76] found upper bounds for the equilateral stick numbers of all prime knots through 10 crossings by using algorithms in the software KnotPlot. In this paper, we find an upper bound on the equilateral stick number of a non-trivial knot K in terms of the minimal crossing number c(K) which is s₌(K) ≤ 2c(K) + 2. Moreover if K is a non-alternating prime knot, then s₌(K) ≤ 2c(K) - 2. Furthermore we find another upper bound on the equilateral stick number for composite knots which is s₌(K₁♯K₂) ≤ 2c(K₁) + 2c(K₂).

Let Len(K) be the minimum length of a knot on the cubic lattice (namely the minimum length necessary to construct the knot in the cubic lattice). This paper provides upper bounds for Len(K) of a nontrivial knot K in terms of its crossing number c(K) as follows:

For a nontrivial knot $K$, Negami found an upper bound on the stick number $s(K)$ in terms of its crossing number $c(K)$ which is $s(K)\le 2c(K)$. Later, Huh and Oh utilized the arc index $\alpha (K)$ to present a more precise upper bound $s(K)\le \frac{3}{2}c(K)+\frac{3}{2}$. Furthermore, Kim, No and Oh found an upper bound on the equilateral stick number $s_{=}(K)$ as follows; $s_{=}(K)\le 2c(K)+2$. As a sequel to this research program, we similarly define the stick number $s(G)$ and the equilateral stick number $s_{=}(G)$ of a spatial graph $G$, and present their upper bounds as follows;

The lattice stick number of knots is defined to be the minimal number of straight sticks in the cubic lattice required to construct a lattice stick presentation of the knot. We similarly define the lattice stick number $s_L(G)$ of spatial graphs $G$ with vertices of degree at most six (necessary for embedding into the cubic lattice), and present an upper bound in terms of the crossing number $c(G)$

According to the third law of Thermodynamics, it takes an infinite number of steps for any object, including black holes, to reach zero temperature. For any physical system, the process of cooling to absolute zero corresponds to erasing information or generating pure states. In contrast with the ordinary matter, the black hole temperature can be lowered only by adding matter–energy into it. However, it is impossible to remove the statistical fluctuations of the infalling matter–energy. The fluctuations lead to the fact that the black holes have a finite lower temperature and, hence, an upper bound on the horizon radius. We make an estimate of the upper bound for the horizon radius which is curiously comparable to Hubble horizon. We compare this bound with known results and discuss its implications.

For a vertex set $S$ of $G$, we use ${\kappa }_S(G)$ to denote the maximum number of edge-disjoint Steiner trees of $G$ such that any two of such trees intersect in $S$. The generalized $k$-connectivity of $G$ is defined as ${\kappa }_k(G)={min}_{S\subseteq V(G),\left|S\right|=k}{\kappa }_S(G)$. We get that for any generalized Petersen graph $G=GP(n,k)$ with $n\ge k+3$, ${\kappa }_t(G)=1$ when $t\ge 2k+5$. We give the values of ${\kappa }_k(G)$ for Petersen graph $GP(5,2)$, where $3\le k\le 10$, and the values of ${\kappa }_k(G)$ for generalized Petersen graph $GP(n,1)$, where $n\ge 3$ and $3\le k\le 2n$.