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.
How to Untangle Complex Systems?
Published in Pier Luigi Gentili, Untangling Complex Systems, 2018
The basic idea of DNA computing is to exploit (1) the bases of DNA strands to encode information and (2) molecular biology tools to make computations. It was Leonard Adleman (1994) who pioneered the field when he solved a small instance of the Hamiltonian Path Problem (commonly known as the Travelling Salesman Problem) solely by manipulating DNA strands in a test tube. The Hamiltonian Path is an example of NP-complete problem (read Chapter 12): given a graph with a certain number of nodes, i.e., given a map with a certain number of cities, and given a certain number of interconnections between nodes, find the path that starts at the start node and ends at the end node and passes through each remaining node exactly once. So far, no one has proposed an algorithm that gives the exact solution in a short time for maps with many nodes (whose number is indicated by N). There are only algorithms that give approximate solutions, achievable in reasonable time. An algorithm of this kind requires the generation of random paths through the graph. Then, for each randomly generated path, it is necessary to follow the instructions reported in the flowchart of Figure 13.8.
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.
Embedding spanning disjoint cycles in augmented cube networks with prescribed vertices in each cycle
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Weiyan Wu, Eminjan Sabir, Hongwei Qiao
A graph G is Hamiltonian if it contains a Hamiltonian cycle, i.e. a cycle containing all vertices of G. A graph G is regarded as Hamiltonian connected if for any pair of distinct vertices u and v, a Hamiltonian path exists. Hamiltonicity and many variations on it have been widely studied, such as k-ordered Hamiltonicity [5], Hamiltonian decomposition [6], pancyclicity [7], spanning connectivity [8], and 2-factors (a 2-factor of a graph G is a spanning 2-regular subgraph of G) [9]. In this paper, we study a relaxation/generalization of the Hamiltonian property. We allow the graph to be spanned by a prescribed number of disjoint cycles. However, each must contain a prescribed vertex. This concept can be applied to the problem of identifying faulty processors and other related issues in interconnection networks [10].
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
Unsupervised Graph-based Discourse Planning and Generation
Published in IETE Technical Review, 2019
Anjali Singh, Niladri Chatterjee
A Hamiltonian path refers to a path in a directed or undirected graph that visits each node exactly once. Like the approach used in [16], the order of triples is found by identifying the most optimal Hamiltonian path (starting from the first triple in the table) in the discourse graph. This accomplishes the task of selecting the order of the triples (nodes) as well as the relations (edges) that connect them. The scheme is explained in the following subsections. However, a fundamental requirement here is to ensure the existence of a Hamiltonian path as Hamiltonian paths are not guaranteed to exist in a graph, the determination of which is an NP-complete problem. Hence, before proceeding further with our algorithm, we study whether the discourse graphs satisfy the conditions for finding a Hamiltonian path through them.