The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
An open problem concerning the computational power of neural networks with symmetric weights is solved. It is shown that these networks possess the same computational power as general networks with asymmetric weights — i.e. these networks can compute any recursive function. The computations of these networks can be described as a minimization process of a certain energy function; it is shown that...
In this paper we discuss the strength of the adversary argument in establishing lower bounds on the complexity of certain sorting-type problems. The relationship between adversary argument and so called information theory argument is indicated and the efficiency of adversary argument relative to the type of comparisons involved in the computation of a problem is investigated. The results concern the...
Using the formalism of Turing machines, efficient deterministic, both sequential and parallel, realizations of nondeterministic computations are described and analyzed. It is shown that when simulating nondeterministic computations by the ring of cooperating Turing machines, the speed-up linear in the number of machines can be achieved as compared to the case of a single machine. Using examples it...
Weak parallel machines represent a new class of physically feasible parallel machine models whose prominent representative is the so-called Parallel Turing Machine (PTM) as introduced by the author in 1984. Except PTMs, further members of this class are e.g. various kinds of systolic machines, cellular automata, orthogonal iterative arrays, etc. From the computational point of view the main common...
It is shown that any RAM of logarithmic time complexity T(n) can be simulated in linear logarithmic time by a RAM that uses only its O(T2(n)/log T(n)) first registers, each of them being of size O(log T(n)). As a consequence such a RAM can also be simulated by a unit cost RAM in time O(U(n)+T(n)/log log T(n)) where U(n) denotes the number of input/output operations of a RAM to be simulated...
An overview of the basic results in complexity theory of discrete neural computations is presented. Especially, the computational power and efficiency of single neurons, neural circuits, symmetric neural networks (Hopfield model), and of Boltzmann machines is investigated and characterized. Corresponding intractability results are mentioned as well. The evidence is presented why discrete neural networks...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.