Search

Possibilistic graphical models are powerful modeling and reasoning tools for uncertain information based on possibility theory. In this paper, we provide an analysis of computational complexity of MAP and MPE queries for possibilistic networks. MAP queries stand for maximum a posteriori explanation while MPE ones stand for most plausible explanation. We show that the decision problems of answering MAP and MPE queries in both min-based and product-based possibilistic networks is NP-complete. Definitely, such results represent an advantage of possibilistic graphical models over probabilistic ones since MAP queries are NPPP -complete in Bayesian networks. Our proofs for querying min-based possibilistic networks make use of reductions from the 3SAT problem to querying possibilistic networks decision problem. Moreover, the provided reductions may be useful for the implementation of MAP and MPE inference engines based on the satisfiability problem solvers. As for product-based networks, the provided proofs are incremental and make use of reductions from SAT and its weighted variant WMAXSAT. [ABSTRACT FROM AUTHOR]

For a formal language L , the problem of language enumeration asks to compute the length-lexicographically smallest word in L larger than a given input w ∈ Σ ∗ (henceforth called the L -successor of w). We investigate this problem for regular languages from a computational complexity and state complexity perspective. We first show that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are (in general) necessary and sufficient for an unambiguous finite-state transducer to compute L -successors. As a byproduct, we obtain that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are sufficient for a DFA to recognize the subset S (L) of L composed of its lexicographically smallest words. We give a matching lower bound that holds even if S (L) is represented as an NFA. It has been known that L -successors can be computed in polynomial time, even if the regular language is given as part of the input (assuming a suitable representation of the language, such as a DFA). In this paper, we refine this result in multiple directions. We show that if the regular language is given as part of the input and encoded as a DFA, the problem is in N L. If the regular language L is fixed, we prove that the enumeration problem of the language is reducible to deciding membership to the Myhill-Nerode equivalence classes of L under D L O G T I M E -uniform A C 0 reductions. In particular, this implies that fixed star-free languages can be enumerated in A C 0 , arbitrary fixed regular languages can be enumerated in N C 1 and that there exist regular languages for which the problem is N C 1 -complete. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the runtime complexity of programs based on multiset rewriting. The motivation behind this work is the study of the complexity of chemistry-inspired programming models, which recently regained momentum due to their adequacy to large autonomous systems. In these models, data are most of the time left unstructured in a container, formally, a multiset. The program to be applied to this multiset is specified as a set of conditioned rules rewriting the multiset. At run time, these rewrite operations are applied concurrently, until no rule can be applied anymore (the set of elements they need cannot be found in the multiset anymore). A limitation of these models stand in their complexity: each computation step may require a complexity in where n denotes the number of elements in the multiset, and k is the size of the subset of elements needed to trigger a given rule. By analogy with chemistry, such elements can be called reactants. In this paper, we explore the possibility of improving the complexity of searching reactants through a static analysis of the rules' condition. In particular, we give a characterisation of this complexity, by analogy to the subgraph isomorphism problem. Given a rule R, we define its rank rk(R) and its calibre C(R), allowing us to exhibit an algorithm with a complexity in for searching reactants, while showing that and that most of the time. [ABSTRACT FROM AUTHOR]

Facing many problems of the urban-rural resident pension insurance system in China, one should firstly make sure that this system can be optimized. This paper, based on the modern control theory, sets up differential equations as models to describe the urban-rural resident pension insurance system, and discusses the globally asymptotic stability in the sense of Liapunov for the urban-rural resident pension insurance system in the new equilibrium point. This research sets the stage for our further discussion, and it is theoretically important and convenient for optimizing the urban-rural resident pension insurance system. [ABSTRACT FROM AUTHOR]

In this paper, we aim to identify a directed complex network with optimal controllability, for which pinning control is to be applied. Since the controllability of a network can be reflected by the smallest nonzero eigenvalue of a matrix related to its topology, an optimal network design problem is formulated based on the maximization of this eigenvalue. To better consider the practical reality, constraints on node degree sequence are specified. Based on the derived bounds of the eigenvalue, an effective rewiring scheme is designed and solutions close to or equal to the upper bound are obtained. Finally, the relationship between network characteristics and controllability is studied. Through complexity analysis, it is concluded that the network with high controllability should possess two properties, i.e. nodes with high out-degree for pinning and other nodes with uniform degree distribution. [ABSTRACT FROM AUTHOR]

Our work is to study the Minimum Latency Broadcast Scheduling problem in the geometric SINR model with power control. With power control, sensor nodes have the ability to adjust transmitting power. While existing works studied the problem assuming a uniform power assignment or allowing unlimited power levels, we investigate the problem with a more realistic power assignment model where the maximum power level is bounded. To the best of our knowledge, no existing work formally proved the NP-hardness, though many researchers have been assuming that this fact holds true. In this paper, we provide a solid proof for this result. [ABSTRACT FROM AUTHOR]

The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations. In this paper, we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of k marked locations for which the number of steps of the algorithm differs by a factor of Ω(k). Second, we present two configurations of k and k marked locations having the same number of steps and probability of finding a marked location. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the central problem of finding recombination events. It is commonly assumed that a present population is a descendent of a small number of specific sequences called founders. The recombination process consists in given two equal length sequences, generates a third sequence of the same length by concatenating the prefix of one sequence with the suffix of the other sequence. Due to recombination, a present sequence (called a recombinant) is thus composed of blocks from the founders. A major question related to founder sequences is the so-called MINIMUM MOSAIC problem: using the natural parsimony criterion for the number of recombinations, find the "best" founders. In this article, we prove that the MINIMUM MOSAIC problem given haplotype recombinants with no missing values is NP-hard when the number of founders is given as part of the input and propose some exact exponential-time algorithms for the problem, which can be considered polynomial provided some extra information. Notice that Rastas and Ukkonen proved that the MINIMUM MOSAIC problem is NP-hard using a somewhat unrealistic mutation cost function. The aim of this paper is to provide a better complexity insight of the problem. [ABSTRACT FROM AUTHOR]

This paper presents a data estimation scheme for wide band multichannel charge sampling filter bank receivers together with a complete system calibration algorithm based on the least mean squared (LMS) algorithm. A unified model has been defined for the receiver containing all first order mismatches, offsets, imperfections, and the LMS algorithm is employed to track these errors. The performance of this technique under noisy channel conditions has been verified. Moreover, a detailed complexity analysis of the calibration algorithm is provided which shows that sinc filter banks have much lower complexity than traditional continuous-time filter banks. [ABSTRACT FROM AUTHOR]

In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. It has been known that the perfect matching problem for the classes of hypergraphs H with minimum ((k - 1)-wise) vertex degreeδ(H) at least c|V(H)| is NP-complete for $c < \frac{1}{k}$ and trivial for c ≥ ½, leaving the status of the problem with c in the interval $[\frac{1}{k}, \frac{1}{2})$ widely open. In this paper we show, somehow surprisingly, that ½ is not the threshold for tractability of the perfect matching problem, and prove the existence of an ε > 0 such that the perfect matching problem for the class of hypergraphs H with δ(H) ≥ (½ - ε)|V(H)| is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest. [ABSTRACT FROM AUTHOR]

Error hypersurfaces are very valuable to study because of their unique status in multilayer perceptron research. Given the architecture of a multilayer perceptron, if the pattern sets are different, so are the respective error hypersurfaces in the multilayer perceptron. Using the theory of groups and Polya Theorem, this paper constructs classes of congruent pattern sets and classes of congruent error hypersurfaces, and proves that the number of classes of congruent pattern sets is equal to the number of congruent error hypersurfaces. Calculation results lead to much fewer classes of congruent error hypersurfaces than the total error hypersurfaces, and show that as the input dimension N increases, the former number increases at a much lower rate than the latter number, thus simplifying the understanding of the complexity of classes of error hypersurfaces. [ABSTRACT FROM AUTHOR]

Recently, the study on the dynamical behavior of complex dynamical systems has become a focal subject in the field of complexity. In particular, the system's adaptability and sensitivity have attracted increasing attention from various scientific communities. In this paper, we focus on some properties of complexity to gain a better understanding of it. Two descriptive mathematical definitions of attractors' adaptability and sensitivity are introduced from the viewpoint of dynamical systems. Then, these new descriptions are applied to analyze the adaptability and sensitivity of stable equilibrium points. In addition, a method is introduced for improving both the adaptability and sensitivity of a system with a stable equilibrium point. [ABSTRACT FROM AUTHOR]

There has been considerable interest in quantifying the complexity of different time series, such as physiologic time series, traffic time series. However, these traditional approaches fail to account for the multiple time scales inherent in time series, which have yielded contradictory findings when applied to real-world datasets. Then multi-scale entropy analysis (MSE) is introduced to solve this problem which has been widely used for physiologic time series. In this paper, we first apply the MSE method to different correlated series and obtain an interesting relationship between complexity and Hurst exponent. A modified MSE method called multiscale permutation entropy analysis (MSPE) is then introduced, which replaces the sample entropy (SampEn) with permutation entropy (PE) when measuring entropy for coarse-grained series. We employ the traditional MSE method and MSPE method to investigate complexities of different traffic series, and obtain that the complexity of weekend traffic time series differs from that of the workday time series, which helps to classify the series when making predictions. [ABSTRACT FROM AUTHOR]

This paper deals with an important problem of mobile communication. The objective is to place k base stations of equal range on the boundary of a convex polygonal region P such that each point inside P is covered by at least one base station. We name this problem as region-cover(k) problem. A simplified form of this problem is the vertex-cover(k) problem, where the objective is to communicate with only the vertices of P instead of covering the entire polygon. We first present efficient algorithms for vertex-cover(2) and region-cover(2) problems, where the base stations are to be installed on a pair of specified edges. The time complexity of these algorithms are O(n log n) and O(n2) respectively, where n is the number of vertices in the polygon P. Next, we consider the case where k ≥ 3. We first concentrate on a restricted version of the vertex-cover(k) and region-cover(k) problems, where all the k base stations are to be installed on the same edge of P. Our proposed algorithm for the restricted vertex-cover(k) problem produces optimum result in O(min(n2,nk log n)) time, whereas the algorithm for the restricted region-cover(k) problem produces an (1 + ∊)-factor approximation result in $O((n + k){\rm log}(n + k) + n{\rm log}(\lceil \frac{1}{\epsilon} \rceil)$ time. Finally, we propose efficient heuristic algorithm for the unrestricted version of the region-cover(k) problem for k ≥ 3. Experimental results demonstrate that our proposed algorithm runs fast and produces near optimum solutions. [ABSTRACT FROM AUTHOR]

A merging procedure joining search pattern and variable block size motion estimation for H.264/AVC is proposed in this paper. The principal purpose of the proposed methods is the reduction of the computational complexity for block matching module. In fact, there are numerous contributions in the literature aiming the reduction of the computational cost needed for motion estimation. The best solution from a qualitative point of view is the full search that considers every possible detail. The computational effort required is enormous and this makes motion estimation by far the most important computational bottleneck in video coding systems. Our approach invests and exploits the center-biased characteristics of the real world video sequences, aiming to achieve an acceptable image quality while independently targeting the reduction of the computational complexity. The simulations results demonstrated that the proposal performs well. [ABSTRACT FROM AUTHOR]

Sparse fuzzy ordering and partial ordering relations have recently become of great importance in the field of knowledge systems. As the size of the relations utilized in such a framework is extremely large, efficient algorithms are needed for their handling. More specifically, when a part of such a relation is updated, the property of transitivity needs to be re-established in timely manner, as the knowledge system often becomes unusable until this process is completed. In this paper we propose two algorithms for the incremental update of fuzzy transitive relations. The first one focuses on the incremental update of a part of an already transitive relation, while the other tackles the complete transitive closure of any relation. For the average sparse relation, both of the proposed algorithms have considerably smaller computational complexity than the classical approach, which we also prove experimentally via application to real life relations of this type. [ABSTRACT FROM AUTHOR]

The paper stresses the universal role that Cellular Nonlinear Networks (CNNs) are assuming today. It is shown that the dynamical behavior of 3D CNN-based models allows us to approach new emerging problems, to open new research frontiers as the generation of new geometrical forms and to establish some links between art, neuroscience and dynamical systems. [ABSTRACT FROM AUTHOR]

On the basis of our previous research, we deepen and complete a kind of macroeconomics IS-LM model with fractional-order calculus theory, which is a good reflection on the memory characteristics of economic variables, we also focus on the influence of the variables on the real system, and improve the analysis capabilities of the traditional economic models to suit the actual macroeconomic environment. The conditions of Hopf bifurcation in fractional-order system models are briefly demonstrated, and the fractional order when Hopf bifurcation occurs is calculated, showing the inherent complex dynamic characteristics of the system. With numerical simulation, bifurcation, strange attractor, limit cycle, waveform and other complex dynamic characteristics are given; and the order condition is obtained with respect to time. We find that the system order has an important influence on the running state of the system. The system has a periodic motion when the order meets the conditions of Hopf bifurcation; the fractional-order system gradually stabilizes with the change of the order and parameters while the corresponding integer-order system diverges. This study has certain significance to policy-making about macroeconomic regulation and control. [ABSTRACT FROM AUTHOR]

This issue is devoted to complex systems in life sciences. Some perspective ideas on possible objectives of future research are extracted from the contents of this issue and brought to the reader's attention. The final ambitious aim is the development of a mathematical theory for complex living systems. [ABSTRACT FROM AUTHOR]

Complex systems are of vast importance in the practical world as well as presenting many theoretical challenges. The measurement of system complexity is still imprecise. For many systems, their modular construction brings challenges in understanding how modules form and the emergent behavior which may result. In other systems, it is the development of encodings and communication protocols which allow complexity to increase dramatically. We take a broad view of these issues and then consider the nature of the system space which generates complexity. We show examples from cellular automata and applications of neural networks to data mining which suggest that complex systems often occupy simple structured sub-spaces. Finally, we look at the way modularity relates to networks and the implications for understanding human cognitive processing. [ABSTRACT FROM AUTHOR]

Agol, Haas and Thurston showed that the problem of determining a bound on the genus of a knot in a 3-manifold, is NP-complete. This shows that (unless P = NP) the genus problem has high computational complexity even for knots in a 3-manifold. We initiate the study of classes of knots where the genus problem and even the equivalence problem have very low computational complexity. We show that the genus problem for alternating knots with n crossings has linear time complexity and is in Logspace (n). Alternating knots with some additional combinatorial structure will be referred to as standard. As expected, almost all alternating knots of a given genus are standard. We show that the genus problem for these knots belongs to T C 0 circuit complexity class. We also show, that the equivalence problem for such knots with n crossings has time complexity n log (n) and is in Logspace (n) and T C 0 complexity classes. [ABSTRACT FROM AUTHOR]

In the high-speed railway wireless communication, a joint channel estimation and signal detection algorithm is proposed for the orthogonal frequency division multiplexing (OFDM) system without cyclic prefix in the doubly-selective fading channels. Our proposed method first combines the basis expansion model (BEM) and the inter symbol interference (ISI) cancellation to overcome the situation that exists with the fast time-varying channel and the normalized maximum multipath channel exceeding the length of the cyclic prefix (CP). At first, the channel estimation and signal detection can be approximated without considering the ISI. Then, the channel parameters and signal detection are updated through ISI cancellation and circular convolution reconstruction from the frequency domain. The simulations show the algorithm can improve the performance of channel estimation and signal detection. [ABSTRACT FROM AUTHOR]

We investigate the possibility to obtain higly multipartite-entangled states as non-degenerate eigenstates of Hamiltonians that involve only short-range and few-body interactions. We study small-size systems (with a number of qubits ranging from three to five) and search for Hamiltonians with a maximally multipartite entangled state (MMES) as a non-degenerate eigenstate. We then find conditions, including bounds on the number of coupled qubits, to build a Hamiltonian with a Greenberger-Horne-Zeilinger (GHZ) state as a non-degenerate eigenstate. We finally comment on possible applications. [ABSTRACT FROM AUTHOR]

Manual acupuncture (MA) is widely used in Traditional Chinese Medicine clinic for pain treatment and controlling stress. To investigate how MA modulates brain activities, electroencephalograph (EEG) signals are recorded with 20 channels by MA at ST36 of right leg in 11 healthy subjects during rest. Two novel nonlinear measures based on ordinal patterns of EEG series, i.e. permutation entropy (PE) and order index (OI), are adopted to investigate the nonlinear complexity characteristic in EEG data at different acupuncture states. It is observed that the recorded EEG series during and after MA have higher PE values and lower OI values compared to before MA. The results show that MA at ST36 can increase EEG complexity, which is especially obvious during MA. Our findings suggest that the PE and OI measures are promising methods to reveal EEG dynamical changes associated with MA stimulus, which could provide a potential for further exploring the interactions between acupuncture and brain activity. Moreover, these preliminary conclusions highlight the beneficial modulations of brain activity by MA, which could contribute to understanding the acupuncture effects on brain, as well as the neurophysiological mechanisms underlying MA. [ABSTRACT FROM AUTHOR]

Computing with words, CWW, is considered in the context of natural language functioning, unifying language with thinking. Previous attempts at modeling natural languages as well as thinking processes in artificial intelligence have met with computational complexity. To overcome computational complexity we use dynamic logic (DL), an extension of fuzzy logic describing fuzzy to crisp transitions. We suggest a possible architecture motivated by mathematical and neural considerations. We discuss the reasons why CWW has to be modeled jointly with thinking and propose an architecture consistent with brain neural structure and with a wealth of psychological knowledge. The proposed architecture implies the existence of relationships between languages and cultures. We discuss these implications for further evolution of English and Chinese cultures, and for cultural effects of interactions between natural languages and CWW. [ABSTRACT FROM AUTHOR]

We use an ecosystem simulator capable of evolving arbitrary neural network topologies to explore the relationship between an information theoretic measure of the complexity of neural dynamics and several graph theoretical metrics calculated for the underlying network topologies. Evolutionary trends confirm and extend previous results demonstrating an evolutionary selection for complexity and small-world network properties during periods of behavioral adaptation. The resultant mapping of the space of network topologies occupied by the most complex networks yields new insights into the relationship between network structure and function. The highest complexity networks are found within limited numerical ranges of clustering coefficient, characteristic path length, small-world index, and global efficiency. The widths of these ranges vary from quite narrow to modest, and provide a guide to the most productive regions of the space of neural topologies in which to search for complexity. Our demonstration that evolution selects for complex dynamics and small-world networks helps explain biological evidence for these trends and provides evidence for selection of these characteristics based purely on network function--with no physical constraints on network structure--thus suggesting that functional and structural evolutionary pressures cooperate to produce brains optimized for adaptation to a complex, variable world. [ABSTRACT FROM AUTHOR]

The quotient complexity, also known as state complexity, of a regular language is the number of distinct left quotients of the language. The quotient complexity of an operation is the maximal quotient complexity of the language resulting from the operation, as a function of the quotient complexities of the operands. The class of star-free languages is the smallest class containing the finite languages and closed under boolean operations and concatenation. We prove that the tight bounds on the quotient complexities of union, intersection, difference, symmetric difference, concatenation and star for starfree languages are the same as those for regular languages, with some small exceptions, whereas Zn -- 1 is a lower bound for reversal. [ABSTRACT FROM AUTHOR]

In the past decades, all of the efforts at quantifying systems complexity with a general tool has usually relied on using Shannon's classical information framework to address the disorder of the system through the Boltzmann-Gibbs-Shannon entropy, or one of its extensions. However, in recent years, there were some attempts to tackle the quantification of algorithmic complexities in quantum systems based on the Kolmogorov algorithmic complexity, obtaining some discrepant results against the classical approach. Therefore, an approach to the complexity measure is proposed here, using the quantum information formalism, taking advantage of the generality of the classical-based complexities, and being capable of expressing these systems' complexity on other framework than its algorithmic counterparts. To do so, the Shiner-Davison-Landsberg (SDL) complexity framework is considered jointly with linear entropy for the density operators representing the analyzed systems formalism along with the tangle for the entanglement measure. The proposed measure is then applied in a family of maximally entangled mixed state. [ABSTRACT FROM AUTHOR]

We define two kinds of invariants of links in closed 3-manifolds, the s-complexity(s ∈ ℕ) and the block number, by considering decompositions of links in closed orientable 3-manifolds by spines. The first one is a generalization of the complexity of links defined by Pervova and Petronio. After providing properties of these invariants, we construct special spines of strongly-cyclic coverings branched over generalized twist knots in lens spaces, including S3 and ℝP3, which provide upper bounds for the invariants. [ABSTRACT FROM AUTHOR]

We prove that in a free group the length of the value of each variable in a minimal solution of a standard quadratic equation is bounded by 2s for an orientable equation and by 12s4 for a non-orientable equation, where s is the sum of the lengths of the coefficients. [ABSTRACT FROM AUTHOR]

Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are modeled by extensions of boolean functions to transients. Formulas for computing the output transient of a gate from the input transients are known for NOT, AND, OR and XOR gates and their complements, but, in general, even the problem of deciding whether the length of the output transient exceeds a given bound is NP-complete. We propose a method of evaluating extensions of general boolean functions. We study a class of functions for which, instead of evaluating the extensions on a given set of transients, it is possible to get the same values by using transients derived from the given ones, but having length at most 3. We prove that all functions of three variables, as well as certain other functions, have this property, and can be efficiently evaluated. [ABSTRACT FROM AUTHOR]

The branch of coding theory that is based on formal languages has produced several methods for defining code properties, including word relations, dependence systems, implicational conditions, trajectories, and language inequations. Of those, the latter three can be viewed as formal methods in the sense that a certain formal expression can be used to denote a code property. Here we present a formal method which is based on transducers. Each transducer of a certain type defines/describes a desired code property. The method provides simple and uniform decision procedures for the basic questions of property satisfaction and maximality for regular languages. Our work includes statements about the hardness of deciding some of the problems involved. It turns out that maximality can be hard to decide even for "classical" code properties of finite languages. We also present an initial implementation of a LAnguage SERver capable of deciding the satisfaction problem for a given transducer code property and regular language. [ABSTRACT FROM AUTHOR]

We discuss models of computing that are beyond classical. The primary motivation is to unearth the cause of non-classical advantages in computation. Completeness results from computational complexity theory lead to the identification of very disparate problems, and offer a kaleidoscopic view into the realm of quantum enhancements in computation. Emphasis is placed on the "power of one qubit" model, and the boundary between quantum and classical correlations as delineated by quantum discord. A recent result by Eastin on the role of this boundary in the efficient classical simulation of quantum computation is discussed. Perceived drawbacks in the interpretation of quantum discord as a relevant certificate of quantum enhancements are addressed. [ABSTRACT FROM AUTHOR]

We investigate the computational complexity of deciding whether or not a given polynomial, presented as the sum of monomials, is identically 0 over a ring. It is proved that if the factor by the Jacobson-radical is not commutative, then the problem is coNP-complete. [ABSTRACT FROM AUTHOR]

The Thompson-Higman groups Gk,i have a natural generalization to monoids, called Mk,i, and inverse monoids, called Invk,i. We study some structural features of Mk,i and Invk,i and investigate the computational complexity of related decision problems. The main interest of these monoids is their close connection with circuits and circuit complexity. The maximal subgroups of Mk,1 and Invk,1 are isomorphic to the groups Gk,j (1 ≤ j ≤ k - 1); so we rediscover all the Thompson-Higman groups within Mk,1. Deciding the Green relations $\leq_{\mathcal J}$ and $\equiv_{\mathcal D}$ of Mk,1, when the inputs are words over a finite generating set of Mk,1, is in P. When a circuit-like generating set is used for Mk,1 then deciding $\leq_{\mathcal J}$ is coDP-complete (where DP is the complexity class consisting of differences of sets in NP). The multiplier search problem for $\leq_{\mathcal J}$ is xNPsearch-complete, whereas the multiplier search problems of $\leq_{\cal R}$ and $\leq_{\cal L}$ are not in xNPsearch unless NP = coNP. The class of search problems xNPsearch is introduced as a slight generalization of NPsearch. Deciding $\equiv_{\mathcal D}$ for Mk,1 when the inputs are words over a circuit-like generating set, is ⊕k-1•NP-complete; for any h ≥ 2, ⊕h•NP is a modular counting complexity class, whose verification problems are in NP. Related problems for partial circuits are the image size problem (which is # • NP-complete), and the image size modulo h problem (which is ⊕h•NP-complete). For Invk,1 over a circuit-like generating set, deciding $\equiv_{\mathcal D}$ is ⊕k-1P-complete. It is interesting that the little known complexity classes coDP and ⊕k-1•NP play a central role in Mk,1. [ABSTRACT FROM AUTHOR]

We study the monoid generalization Mk, 1 of the Thompson–Higman groups, and we characterize the ${\mathcal R}$- and the ${\mathcal L}$-order of Mk, 1. Although Mk, 1 has only one nonzero $\mathcal J$-class and k-1 nonzero $\mathcal D$-classes, the $\mathcal R$- and the $\mathcal L$-order are complicated; in particular, $\langle_{\mathcal R}$ is dense (even within an $\mathcal L$-class), and $\langle_{\mathcal L}$ is dense (even within an $\mathcal R$-class). We study the computational complexity of the ${\mathcal R}$- and the ${\mathcal L}$-order. When inputs are given by words over a finite generating set of Mk, 1, the ${\mathcal R}$- and the ${\mathcal L}$-order decision problems are in P. However, over a "circuit-like" generating set the ${\mathcal R}$-order decision problem of Mk, 1 is $\Pi_2^{\sf P}$-complete, whereas the ${\mathcal L}$-order decision problem is coNP-complete. Similarly, for acyclic circuits the surjectiveness problem is $\Pi_2^{\sf P}$-complete, whereas the injectiveness problem is coNP-complete. [ABSTRACT FROM AUTHOR]

We discuss time complexity of the Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group. [ABSTRACT FROM AUTHOR]

The emergence of complexity is investigated from the viewpoint of the energy balance property and the divergence property of reaction–diffusion cellular neural networks. [ABSTRACT FROM AUTHOR]