Abstract: The problem is to calculate an approximate solution of an initial value problem for an autonomous system of N ordinary differential equations. Using fast power series techniques, we exhibit an algori...
详细信息
Abstract: The problem is to calculate an approximate solution of an initial value problem for an autonomous system of N ordinary differential equations. Using fast power series techniques, we exhibit an algorithm for the pth-order Taylor series method requiring only $O({p^N}\ln p)$ arithmetic operations per step as $p \to + \infty$. (Moreover, we show that any such algorithm requires at least $O({p^N})$ operations per step.) We compute the order which minimizes the complexity bounds for Taylor series and linear Runge-Kutta methods and show that in all cases this optimal order increases as the error criterion $\varepsilon$ decreases, tending to infinity as $\varepsilon$ tends to zero. Finally, we show that if certain derivatives are easy to evaluate, then Taylor series methods are asymptotically better than linear Runge-Kutta methods for problems of small dimension N.
We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient m...
详细信息
We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices.
We exhibit finite algebras each generating a variety with NP-complete finite algebra membership problem. The smallest of these algebras is the flat graph algebra belonging to the tetrahedral graph, a graph of 6 vertic...
详细信息
We exhibit finite algebras each generating a variety with NP-complete finite algebra membership problem. The smallest of these algebras is the flat graph algebra belonging to the tetrahedral graph, a graph of 6 vertices obtained by cutting and spreading out the surface of a tetrahedron on the plane. The sequence of graphs we use to build up our flat graph algebras is similar to the sequence exhibited by Wheeler in [36], 1979, to describe the first order theory of k-colorable graphs. Graph algebras wen introduced by Shallon in [34], 1979, and investigated, among others, by Baker, McNulty and Werner in [2], 1987. Flat algebras were constructed and used by McKenzie in [27], 1996, to settle some open questions related to decidability, like Tarski's Finite Basis Problem. Flat graph algebras were also discussed by Willard in [37], 1996, and Delic in [8], 1998.
There exist constructive correspondences between Turing machines having finitely determinable behavior and computable probability measures on their output sequences. These correspondences determine limits on the relat...
详细信息
Some parameters related to the computational complexity of partitioned list algorithms are evaluated. Specifically, an upper bound is computed for the average number of comparisons needed by the most unsophisticated v...
详细信息
Some parameters related to the computational complexity of partitioned list algorithms are evaluated. Specifically, an upper bound is computed for the average number of comparisons needed by the most unsophisticated version of a partitioned list algorithm for processing a Boolean function in v variables and u canonical clauses. For the same functions the average memory size required for processing is also computed. Furthermore the minimum memory size necessary for processing any Boolean function in u canonical clauses by either a partitioned or a nonpartitioned list algorithm is computed. Results obtained from the above comparisons demonstrate that partitioned list algorithms compare favorably with nonpartitioned ones both with regard to the time and the memory required for computation.
We propose a new approach for multiverse analysis based on computational complexity, which leads to a new family of "computational" measure factors. By defining a cosmology as a spacetime containing a vacuum...
详细信息
We propose a new approach for multiverse analysis based on computational complexity, which leads to a new family of "computational" measure factors. By defining a cosmology as a spacetime containing a vacuum with specified properties (for example small cosmological constant) together with rules for how time evolution will produce the vacuum, we can associate global time in a multiverse with clock time on a supercomputer which simulates it. We argue for a principle of "limited computational complexity" governing early universe dynamics as simulated by this supercomputer, which translates to a global measure for regulating the infinities of eternal inflation. The rules for time evolution can be thought of as a search algorithm, whose details should be constrained by a stronger principle of "minimal computational complexity". Unlike previously studied global measures, ours avoids standard equilibrium considerations and the well-known problems of Boltzmann Brains and the youngness paradox. We also give various definitions of the computational complexity of a cosmology, and argue that there are only a few natural complexity classes. (C) 2018 Elsevier Inc. All rights reserved.
This paper presents an overview of results related to the computational complexity of network reliability analysis problems. Network reliability analysis problems deal with the determination of reliability measures fo...
详细信息
This paper presents an overview of results related to the computational complexity of network reliability analysis problems. Network reliability analysis problems deal with the determination of reliability measures for stochastic networks. We show how these problems are related to the more familiar computational network problems of recognizing certain subnetworks, finding optimal subnetworks, and counting certain subnetworks. We use these relationships to show that the k-terminal, the 2-terminal, and the all-terminal network reliability analysis problems are at least as hard as the renowned set of computationally difficult problems, NP-Complete. Finally, we discuss the impact of these results on how one should approach problem solving in this area.
A class of combinatorial optimization problems related to optimal pattern recognition learning is studied by the method of structural risk minimization in the class of piecewise linear committee decision rules. Most o...
详细信息
The computational complexity of a new class of combinatorial optimization problems that are induced by optimal machine learning procedures in the class of collective piecewise linear classifiers of committee type is s...
详细信息
The computational complexity of a new class of combinatorial optimization problems that are induced by optimal machine learning procedures in the class of collective piecewise linear classifiers of committee type is studied.
Computability and computational complexity were first considered over the fields of real and complex numbers and generalized to arbitrary algebraic systems. This article approaches the theory of computational complexi...
详细信息
Computability and computational complexity were first considered over the fields of real and complex numbers and generalized to arbitrary algebraic systems. This article approaches the theory of computational complexity over an arbitrary algebraic system by taking computability over the list extension for a computational model of it. We study the resultant polynomial complexity classes and mention some NP-complete problems.
暂无评论