China
Africa
Explore chapters and articles related to this topic
Number-Theoretic Reference Problems
Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
In 1994, Shor [1128] conceived randomized polynomial-time algorithms for computing discrete logarithms and factoring integers on a quantum computer, a computational device based on quantum mechanical principles; presently it is not known how to build a quantum computer, nor if this is even possible. Also recently, Adleman [10] demonstrated the feasibility of using tools from molecular biology to solve an instance of the directed Hamiltonian path problem, which is NP-complete. The problem instance was encoded in molecules of DNA, and the steps of the computation were performed with standard protocols and enzymes. Adleman notes that while the currently available fastest supercomputers can execute approximately 1012 operations per second, it is plausible for a DNA computer to execute 1020 or more operations per second. Moreover such a DNA computer would be far more energy-efficient than existing supercomputers. It is not clear at present whether it is feasible to build a DNA computer with such performance. However, should either quantum computers or DNA computers ever become practical, they would have a very significant impact on public-key cryptography.
Applications
Published in James J Y Hsu, Nanocomputing, 2017
DNA computation, or computation with DNA molecules, was demonstrated with a molecular algorithm (Adeleman 1994) to solve Hamiltonian path problem. The idea of biologically-inspired molecular computation leads to many new research. Turing computability and computational complexity of molecular reactions were studied in relation to formal language theory. The inherent computational power of molecules through self-organization or self-assembly, as a new paradigm for computation was investigated both theoretically and experimentally. The mesoscopic biology, chemistry and physics will be the basis for a more general computational paradigm in this regard, and the computations are interpreted as the outcome arising out of deterministic and stochastic interactions among elements in a multiset object-space which includes the environment. The nonlinear computing of neuron network, the heuristic and fuzzy logic, and the biological-based linguistic and reasoning are a few noticeable distinct characteristics. These may well have been demonstrated from the”Savant”— meaning ‘knowing’ in French as an exceptional genius. The distinctions of molecular computers from the silicon-based computers are many, and even the molecular IO — input and output devices are beyond the current human technology.
Introduction
Published in Vlad P. Shmerko, Svetlana N. Yanushkevich, Sergey Edward Lyshevski, Computer Arithmetics for Nanoelectronics, 2018
Vlad P. Shmerko, Svetlana N. Yanushkevich, Sergey Edward Lyshevski
Topic 4: DNA computing. The first successful experiment involving the use of DNA molecules and DNA manipulation techniques was reported by L. M. Adelman in 1994 [2]. He proposed the solution of a small instance of the Hamiltonian path problem in a directed graph. The Hamiltonian path problem has been shown to be an NP-complete problem, that is, intractable in the traditional computing paradigm. To solve this problem, Adleman developed the algorithm and encoded this algorithm step by step using DNA molecular structures. He showed that this NP-complete problem can be solved in linear time due to the massive parallelism of DNA computing.
Multi-product continuous plant scheduling: combination of decomposition, genetic algorithm, and constructive heuristic
Published in International Journal of Production Research, 2020
Pavel Borisovsky, Anton Eremeev, Josef Kallrath
The problem asks to choose the set of tasks to be performed and to schedule them so that all the demands are fulfilled, and and time limits are satisfied. As a primary optimisation criterion we chose the minimisation of the completion time of the last task (makespan) denoted by . The problem is NP-hard because, as well as the initial problem, it includes the Hamiltonian Path problem as a special case. Even if all changeover durations are equal, this problem is shown to be NP-hard for any given number of products in case the execution time of each task has a lower limit and an upper time limit , the production rate of each unit is product independent, and all demands are equal (Dolgui et al. 2010). An exact algorithm for solving this problem, in case the changeover times satisfy the triangle inequality, may be found in Dolgui et al. (2010). The time complexity of this algorithm is exponential in and , here and below denotes the set of tasks that can be performed on a unit
Longest (s, t)-paths in L-shaped grid graphs
Published in Optimization Methods and Software, 2019
Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri
The longest path problem, that is, the problem of finding a simple path with the maximum number of vertices, is one of the most important problems in graph theory. The well-known NP-complete Hamiltonian path problem, that is, deciding whether there is a simple path that visits each vertex of the graph exactly once, is a special case of the longest path problem and has many applications [6,7,11]. Despite the many applications of the problem, it is still open for some classes of graphs, including solid grid graphs and grid graphs with some holes [21,29].