We explore a new graph parameter, KLX number, which quantifies the minimum edge congestion of depth-first search (DFS) traversals of a given graph. Originally motivated by a problem in RNA nanostructure design, this parameter is also of independent theoretical interest. Informally, the KLX number of a graph is defined as the minimum, over all its DFS traversals, of the maximum number of back edges that are simultaneously open during the traversal. We provide full characterisations and linear-time recognition algorithms for graphs with KLX numbers 0, 1 and 2. We also relate KLX to tree-width, proving that any graph satisfies TW ≤ KLX+1. Furthermore, we show that the property KLX ≤ k is MSO₂-expressible for every fixed k. Combined with the tree-width bound, this result implies that determining whether a graph has KLX number at most k can be achieved in linear time for any constant k.

Abstract The aim of this work was to develop a technique to speed up complex joins in an incremental visual query system. When designing a visual, highly interactive interface for ad-hoc (read-only) queries, fast response times are of paramount importance. While a column-oriented DBMS reduces the inherent latency found in relational DBMS, there is still the question of how to index the data, especially so as to support complex joins. Equi-joins that involve a many-to-many relationship are an example of complex joins that arise frequently and whose efficient processing is essential for fast query processing. We present OVI-3, a NoSQL visual query system based on incremental querying that uses a simple directory-based indexing scheme for faster processing of such complex joins. The system has been piloted using real data from a student database at Aalto University. The results demonstrated that for certain complex joins the presented indexing scheme outperforms SQL queries from a data server, especially for queries involving anti-joins (negation), where OVI-3 provided an orders of magnitude speed improvement.

BACKGROUND: Predicting the secondary, i.e. base-pairing structure of a folded RNA strand is an important problem in synthetic and computational biology. First-principle algorithmic approaches to this task are challenging because existing models of the folding process are inaccurate, and even if a perfect model existed, finding an optimal solution would be in general NP-complete. RESULTS: In this paper, we propose a simple, yet effective data-driven approach. We represent RNA sequences in the form of three-dimensional tensors in which we encode possible relations between all pairs of bases in a given sequence. We then use a convolutional neural network to predict a two-dimensional map which represents the correct pairings between the bases. Our model achieves significant accuracy improvements over existing methods on two standard datasets, RNAStrAlign and ArchiveII, for 10 RNA families, where our experiments show excellent performance of the model across a wide range of sequence lengths. Since our matrix representation and post-processing approaches do not require the structures to be pseudoknot-free, we get similar good performance also for pseudoknotted structures. CONCLUSION: We show how to use an artificial neural network design to predict the structure for a given RNA sequence with high accuracy only by learning from samples whose native structures have been experimentally characterized, independent of any energy model.

We consider the problem of maximizing the lifetime of a given multicast connection in a wireless network of energy-constrained (e.g., battery-operated) nodes, by choosing ideal transmission power levels for the nodes relaying the connection. We distinguish between two basic operating modes: In a static power assignment, the power levels of the nodes are set at the beginning and remain unchanged until the nodes are depleted of energy. In a dynamic power schedule, the powers can be adjusted during operation. We show that while lifetime-maximizing static power assignments can be found in polynomial time, for dynamic schedules the problem becomes NP-hard. We introduce two approximation heuristics for the dynamic case, and experimentally verify that the lifetime of a dynamically adjusted multicast connection can be made several times longer than what can be achieved by the best possible static assignment.

We establish a fundamental result in the theory of computation by continuous-time dynamical systems by showing that systems corresponding to so-called continuous-time symmetric Hopfield nets are capable of general computation. As is well known, such networks have very constrained Lyapunov-function controlled dynamics. Nevertheless, we show that they are universal and efficient computational devices, in the sense that any convergent synchronous fully parallel computation by a recurrent network of n discrete-time binary neurons, with in general asymmetric coupling weights, can be simulated by a symmetric continuous-time Hopfield net containing only 18n + 7 units employing the saturated-linear activation function. Moreover, if the asymmetric network has maximum integer weight size w(max) and converges in discrete time t*, then the corresponding Hopfield net can be designed to operate in continuous time Theta(t*/epsilon) for any epsilon > 0 such that w(max)2(12n) </= epsilon2(1/epsilon). In terms of standard discrete computation models, our result implies that any polynomially space-bounded Turing machine can be simulated by a family of polynomial-size continuous-time symmetric Hopfield nets.

We survey and summarize the literature on the computational aspects of neural network models by presenting a detailed taxonomy of the various models according to their complexity theoretic characteristics. The criteria of classification include the architecture of the network (feedforward versus recurrent), time model (discrete versus continuous), state type (binary versus analog), weight constraints (symmetric versus asymmetric), network size (finite nets versus infinite families), and computation type (deterministic versus probabilistic), among others. The underlying results concerning the computational power and complexity issues of perceptron, radial basis function, winner-take-all, and spiking neural networks are briefly surveyed, with pointers to the relevant literature. In our survey, we focus mainly on the digital computation whose inputs and outputs are binary in nature, although their values are quite often encoded as analog neuron states. We omit the important learning issues.

We establish a fundamental result in the theory of computation by continuous-time dynamical systems, by showing that systems corresponding to so called continuous-time symmetric Hopfield nets are capable of general computation. More precisely, we prove that any function computed by a discrete-time asymmetric recurrent network of n threshold gates can also be computed by a continuous-time symmetrically-coupled Hopfield system of dimension 18n+7. Moreover, if the threshold logic network has maximum weight w_{\max} and converges in discrete time t^*, then the corresponding Hopfield system can be designed to operate in continuous time Θ(t^*/ε), for any value 0<ε<0.0025 such that w_{\max}2^{3n}\leq\ε 2^{1/ε}.

We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this problem in the case of binary nets. Finally, we show that symmetric analog nets with an external clock are computationally Turing universal.

We introduce a model for analog computation with discrete time in the presence of analog noise that is flexible enough to cover the most important concrete cases, such as noisy analog neural nets and networks of spiking neurons. This model subsumes the classical model for digital computation in the presence of noise. We show that the presence of arbitrarily small amounts of analog noise reduces the power of analog computational models to that of finite automata, and we also prove a new type of upper bound for the VC-dimension of computational models with analog noise.

We prove that polynomial size discrete Hopfield networks with hidden units compute exactly the class of Boolean functions PSPACE/poly, i.e., the same functions as are computed by polynomial space-bounded nonuniform Turing machines. As a corollary to the construction, we observe also that networks with polynomially bounded interconnection weights compute exactly the class of functions P/poly, i.e., the class computed by polynomial time-bounded nonuniform Turing machines.

We introduce a measure for the computational complexity of mdiwdual instances of a decision problem and study some of Its properties.The instance complexity of a string ~with respect to a set A and time bound t, ict(x : A). is defined as the size of the smallest special-case program for A that run> m time t,decides x correctly, and makes no mistakes on other strings ("don't know" answers are permitted).We prove that a set A is m P if and only if there exist a polynomial t and a constant c such that ic'(x : A) < c for all X; on the other hand, If A ]s NP-hard and P # NP, then for all polynomials t and constants c. lc'(~: A) > c log I ~I for ]nfimtely many x.Obserwng that Kf(x), the t-bounded Kolmogorov complexity of x, N roughly an upper bound on ]Ct(.t: A), we proceed to investigate the existence of mdiwdually hard problem Instances.].e , strings whose instance complexity E close to their Kolmogorov complexity.We prove that if t(n) z n is a time-constructible function and A 1s a recurswe set not in DTIME(t), there then exist a constant c and mfimtely many I such that ic'(x : ,4) z K' (x) -c. for some Prehmmary versions of parts of this work have appeared under the titles "What 1s a hard instance of a computational problem?" m Proceedings of tize Conference on Structare m Cornplexm Theory (Berkeley, Calif., June i 986), and "On the instance complexity of NP-hard problems" in Procecduzgs of the 5tk .4nrrualConference on StntctLwe m Cowrpkwty Theory (Barcelona, Spain, July 1990).

We prove that it is an NP-hard problem to determine the attraction radius of a stable vector in a binary Hopfield memory network, and even that the attraction radius is hard to approximate. Under synchronous updating, the problems are already NP-hard for two-step attraction radii; direct (one-step) attraction radii can be computed in polynomial time.

A scheme is presented for translating high-level descriptions of conceptual hierarchies into a neural network representation. The intuitive semantics of a conceptual hierarchy is provided by a Bayesian net, and the neural network implementation provably approximates the behavior of this net under a stochastic simulation rule

The notion of “lowness” was introduced in computational complexity theory by Schöning [J, Comput. Systems Sci., 27 (1983), pp. 14–28] who studied sets in the class NP. This notion may be interpreted as setting an upper bound on the amount of information that can be encoded by a set. Here ideas from previous studies are incorporated in order to capture the notion of a set being exponentially low. The main result asserts the existence of a sparse set E such that ${\operatorname{DEXT}}(E) = {\operatorname{DEXT}}$, i.e., E is “exponentially low,” but E is not in the class P. In contrast, any set with small generalized Kolmogorov complexity that is exponentially low must be in the class P. In addition, we show that for each $k \geqq 2$, any sparse set S that is low with respect to the class $\Sigma _k^E $ of the exponential-time hierarchy (i.e., $\Sigma _k^E {(S) = \Sigma _k^E } $ ) must be in the class $\Sigma _k^P $ of the polynomial-time hierarchy. Similarly, for each $k \geqq 4$, any set with polynomial-size circuits that is low with respect to the class $\Sigma _k^E $ must be in the class $\Sigma _k^P $ .

A set A not in P is polynomially levelable if any algorithm for A has speedup to a polynomial infinitely often in A: precisely, if given any algorithm M for A and polynomial p, it is possible to find another algorithm $M'$ for A and polynomial $p'$, such that $M'$ runs in time $p'(|x|)$ on infinitely many inputs x in A, on which the running time of M exceeds $p(|x|)$. Intuitively, this condition states that among polynomial time computable approximations to A there is no optimal one, or one giving correct answers on a maximally large subset of A. It appears that most naturally occurring intractable sets are polynomially levelable. We prove this for sets not in P that are either “paddable,” “self-reducible,” or complete for a deterministic time class. We also discuss levelability preserving reductions, and give a simple reducibility characterization of nonlevelable sets.