Neuromorphic computing has several characteristics that make it an extremely compelling computing paradigm for post Moore computation. Some of these characteristics include intrinsic parallelism, inherent scalability,...
详细信息
In this paper we prove that the avalanche problem for the Kadanoff sandpile model (KSPM) is P-complete for two-dimensions. Our proof is based on a reduction from the monotone circuit value problem by building logic ga...
详细信息
ISBN:
(纸本)9789521225031
In this paper we prove that the avalanche problem for the Kadanoff sandpile model (KSPM) is P-complete for two-dimensions. Our proof is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with configurations in KSPM. The proof is also related to the known prediction problem for sandpile which is in NC for one-dimensional sandpiles and is P-complete for dimension 3 or greater. The computational complexity of the prediction problem remains open for two-dimensional sandpiles.
Evolutionary algorithms and other nature-inspired search heuristics like ant colony optimization have been shown to be very successful when dealing with real-world applications or problems from combinatorial optimizat...
详细信息
ISBN:
(纸本)9781605581309
Evolutionary algorithms and other nature-inspired search heuristics like ant colony optimization have been shown to be very successful when dealing with real-world applications or problems from combinatorial optimization. In recent years, analyses has shown that these general randomized search heuristics can be analyzed like "ordinary" randomized algorithms and that such analyses of the expected optimization time yield deeper insights in the functioning of evolutionary algorithms in the context of approximation and optimization. This is an important research area where a lot of interesting questions are still *** tutorial enables attendees to analyze the computational complexity of evolutionary algorithms and other search heuristics in a rigorous way. An overview of the tools and methods developed within the last 15 years is given and practical examples of the application of these analytical methods are presented.
The exact computation of orbits of discrete dynamical systems on the interval is considered. Therefore, a multiple-precision floating point approach based on error analysis is chosen and a general algorithm is present...
详细信息
The exact computation of orbits of discrete dynamical systems on the interval is considered. Therefore, a multiple-precision floating point approach based on error analysis is chosen and a general algorithm is presented. The correctness of the algorithm is shown and the computational complexity is analyzed. As a main result, the computational complexity measure considered here is related to the Ljapunow exponent of the dynamical system under consideration.
A computation consists of algorithm of basic operations. When you consider an algorithm, you assume, say, the standard RAM model, that has "usual" arithmetic operations. On the other hand, when you consider ...
详细信息
ISBN:
(纸本)9783662476659
A computation consists of algorithm of basic operations. When you consider an algorithm, you assume, say, the standard RAM model, that has "usual" arithmetic operations. On the other hand, when you consider an algorithm on a DNA computer, your basic operations are duplication and inversion on a string. Then you need to consider completely different algorithms, and their computational complexity also changes. That is, when we discuss computational complexity of a problem, it strongly depends on the set of basic operations you use. When you enjoy a puzzle, you have to find an algorithm by combining reasonable basic operations to its goal. (Some puzzles require to find the basic operations themselves, but we do not consider such puzzles in this talk.) From the viewpoint of theoretical computer science, puzzles give us some insight to computation and computational complexity classes in various way. Some puzzles and games give reasonable characterizations to computational complexity classes. For example, "pebble game" is a classic model that gives some complexity classes in a natural way, and "constraint logic" is recent model that succeeds to solve a long standing open problem due to Martin Gardner that asks the computational complexity of sliding block puzzles. Such puzzles gives us "typical" and characterization and "intuitive" understanding for some computational complexity classes. On the other hand, there are some puzzles and games that give nontrivial interesting aspects of computational complexity classes. For example, consider"14-15 puzzle" which is classic well known sliding puzzle. By parity, we can determine if one arrangement can be slid to the other in linear time. Moreover, we can always find a way for sliding between them in quadratic time. However, interestingly, finding the optimal solution is NP-complete in general. I also introduce a relatively new notion of the reconfiguration problem. This series of new problems will give some new notion of computat
This paper dose the theoretical analysis for solving the algorithm complexity of a neural network using rational cubic spline weight functions with linear denominator. It concludes that the time complexity of the trai...
详细信息
Evolutionary algorithms and other nature-inspired search heuristics like ant colony optimization have been shown to be very successful when dealing with real-world applications or problems from combinatorial optimizat...
详细信息
We investigate the computational complexity of a simple one-dimensional origami problem. We are given a paper strip P of length n+1 and fold it into unit length by creasing at unit intervals. Consequently, we have sev...
详细信息
The (group) no-show paradox refers to the undesirable situation where a group of agents has the incentive to abstain from voting to get a more favorable winner. We examine the computational complexity of verifying whe...
详细信息
5G mobile communication using a high carrier frequency can operate a massive array antenna. A large-scale antenna element is a major factor that increases the hardware and software complexity of an array antenna. In s...
详细信息
暂无评论