Dynamical analysis,circuit realization,and application in pseudorandom number generators of a fractional-order laser chaotic system

A new five-dimensional fractional-order laser chaotic system (FOLCS) is constructed by incorporating complex variables and fractional calculus into a Lorentz-Haken-type laser system. Dynamical behavior of the system, circuit realization and application in pseudorandom number generators are studied. Many types of multi-stable states are discovered in the system. Interestingly, there are two types of state transition phenomena in the system, one is the chaotic state degenerates to a periodical state, and the other is the intermittent chaotic oscillation. In addition, the complexity of the system when two parameters change simultaneously is measured by the spectral entropy algorithm. Moreover, a digital circuit is design and the chaotic oscillation behaviors of the system are verified on this circuit. Finally, a pseudo-random sequence generator is designed using the FOLCS, and the statistical characteristics of the generated pseudo-random sequence are tested with the NIST-800-22. This study enriches the research on the dynamics and applications of FOLCS.     

A Structural Entropy Measurement Principle of Propositional Formulas in Conjunctive Normal Form

The satisfiability (SAT) problem is a core problem in computer science. Existing studies have shown that most industrial SAT instances can be effectively solved by modern SAT solvers while random SAT instances cannot. It is believed that the structural characteristics of different SAT formula classes are the reasons behind this difference. In this paper, we study the structural properties of propositional formulas in conjunctive normal form (CNF) by the principle of structural entropy of formulas. First, we used structural entropy to measure the complex structure of a formula and found that the difficulty solving the formula is related to the structural entropy of the formula. The smaller the compressing information of a formula, the more difficult it is to solve the formula. Secondly, we proposed a λ-approximation strategy to approximate the structural entropy of large formulas. The experimental results showed that the proposed strategy can effectively approximate the structural entropy of the original formula and that the approximation ratio is more than 92%. Finally, we analyzed the structural properties of a formula in the solution process and found that a local search solver tends to select variables in different communities to perform the next round of searches during a search and that the structural entropy of a variable affects the probability of the variable being flipped. By using these conclusions, we also proposed an initial candidate solution generation strategy for a local search for SAT, and the experimental results showed that this strategy effectively improves the performance of the solvers CCAsat and Sparrow2011 when incorporated into these two solvers.     

Potts models with magnetic field: Arithmetic,geometry, and computation

We give a sheaf theoretic interpretation of Potts models with external magnetic field, in terms of constructible sheaves and their Euler characteristics. We show that the polynomial countability question for the hypersurfaces defined by the vanishing of the partition function is affected by changes in the magnetic field: elementary examples suffice to see non-polynomially countable cases that become polynomially countable after a perturbation of the magnetic field. The same recursive formula for the Grothendieck classes, under edge-doubling operations, holds as in the case without magnetic field, but the closed formulae for specific examples like banana graphs differ in the presence of magnetic field. We give examples of computation of the Euler characteristic with compact support, for the set of real zeros, and find a similar exponential growth with the size of the graph. This can be viewed as a measure of topological and algorithmic complexity. We also consider the computational complexity question for evaluations of the polynomial, and show both tractable and NP-hard examples, using dynamic programming.     

Feedback controlled periodic states for different kinds of photorefractive nonlinear response

We investigate analytically and numerically the influence of the type of the photorefractive nonlinear response on the periodic states (attractors) which occur during feedback controlled 2W-coupling and correspond to almost 100% diffraction efficiency of the dynamic index grating. In addition to the case of the local response typical, for example, for LiNbO₃ crystals we consider the cases of nonlocal (diffusive) response (BaTiO₃, SBN) and resonant response (DC-biased BSO, BTO, and BGO crystals). It is shown that the conditions for the transition to the periodic states and their apparent characteristics are strongly different for the two limiting cases above. Received 16 July 2002 / Received in final form 29 October 2002 Published online 4 March 2003     

束晕-混沌的复杂性理论与控制方法及其应用前景

本文系统论述涉及强流加速器等强流离子束装置中产生的束晕-混沌的复杂性理论与控制方法及其应用前景。强流离子束在核材料生产与增殖、洁净核能、放射性废物嬗变、放射性药物生产、重离子聚变、高能物理、核科学与工程、国防与民用工业和医疗等许多方面都有极其重要的应用潜力和诱人的发展前景。尤其是，近年来强流加速器驱动的放射性洁净核能系统是国内外关注的热门课题，因为它比常规核电更安全、更干净、更便宜。但是，强流离子束形成的束晕-混沌的复杂性现象已引起了国内外广泛关注，需要加以抑制、控制和消除这类现象，解决这一难题已经成为强流离子束应用中的关键问题之一。目前不仅必须深入研究这类束晕-混沌的复杂特性及其产生的物理机制，而且需要研究如何实现对束晕-混沌的有效控制，并寻求和发展其新理论、新方法和新技术。这就向强流离子束物理和非线性-复杂性科学及其技术提出了一系列极富挑战性的新课题。本文结合国内外的研究概况，根据我们多年来的研究成果，特别是我们首创性地提出了一些束晕-混沌的有效控制方法，它们包括：非线性反馈控制法，小波反馈控制法，变结构控制法，延迟反馈控制法，参数自适应控制法等，进行重点的介绍。对上述课题当前的主要进展及相关问题进行系统的总结和比较全面综述的评论。最后，指出该领域今后的研究方向，以推动这个崭新领域的深入研究和应用发展。     

On the counting function of the lattice profile of periodic sequences

The lattice profile analyzes the intrinsic structure of pseudorandom number sequences with applications in Monte Carlo methods and cryptology. In this paper, using the discrete Fourier transform for periodic sequences and the relation between the lattice profile and the linear complexity, we give general formulas for the expected value, variance, and counting function of the lattice profile of periodic sequences with fixed period. Moreover, we determine in a more explicit form the expected value, variance, and counting function of the lattice profile of periodic sequences for special values of the period.     

匹配问题实例空间和解空间结构

本文通过研究匹配问题的实例空间，匈牙利算法和解空间三者之间的关系，指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的，而如何对问题的解空间进行合理的分解才能是问题的关键。     

On the Linear Complexity Profile of Nonlinear Congruential Pseudorandom Number Generators with Dickson Polynomials

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and Monte-Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. Recently, a weak lower bound on the linear complexity profile of a general nonlinear congruential pseudorandom number generator was proven by Gutierrez, Shparlinski and the first author. For most nonlinear generators a much stronger lower bound is expected. Here, we obtain a much stronger lower bound on the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials.     

Orderings of uniquely colorable hypergraphs

For a mixed hypergraph H=(X,C,D), where C and D are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every C∈C meets some class in more than one vertex, and every D∈D has a nonempty intersection with at least two classes. A vertex-orderx₁,x₂,…,x_n on X (n=|X|) is uniquely colorable if the subhypergraph induced by {x_j:1?j?i} has precisely one coloring, for each i (1?i?n). We prove that it is NP-complete to decide whether a mixed hypergraph admits a uniquely colorable vertex-order, even if the input is restricted to have just one coloring. On the other hand, via a characterization theorem it can be decided in linear time whether a given color-sequence belongs to a mixed hypergraph in which the uniquely colorable vertex-order is unique.