China
Africa
Explore chapters and articles related to this topic
The Longer Term: Quantum Information Processing and Communication
Published in Simon Deleonibus, Electronic Device Architectures for the Nano-CMOS Era, 2019
Integer factoring is a special case of a larger class of problems (called the “Hidden Subgroup Problem”) which can also benefit from an exponential speedup when an adequate form of Shor’s Quantum Fourier Transform exists. Such a QFT is known to exist when the problem domain is a commutative group (e.g. integers modulo P, for factoring). Research is currently very active for extending Shor’s approach to non commutative groups. A few very specific problems in this larger class have been solved polynomially, but no general solution is known yet. One of the challenges is finding a polynomial algorithm for graph isomorphism, which is a problem of very high interest in many domains.
Graph Edit Distance—Theory, Algorithms, and Applications
Published in Olivier Lézoray, Leo Grady, Image Processing and Analysis with Graphs, 2012
It is still an open question whether the graph isomorphism problem belongs to the NP class or not. Polynomial algorithms have been developed for special classes of graphs such as bounded valence graphs [23] (i.e., graphs where the maximum number of edges adjacent to a node is bounded by a constant); planar graphs [24] (i.e., graphs that can be drawn on a plane without graph edges crossing) and trees [11] (i.e., graphs with no cycles). But no polynomial algorithms are known for the general case. Conversely, the subgraph isomorphism problem is proven to be NP-complete [25].
A Quantum Resistant Chameleon Hashing and Signature Scheme
Published in IETE Journal of Research, 2022
As to find collision on h, the adversary has to try two basic attacks; first, try to recover the secret key H from and second, he might attempt to find collision on h without recovering H. The first attack is the structural attack against general Goppa codes and as pointed out in [19], the only structural attack is the support splitting algorithm (SSA) [20]. For a given public key, the SSA does not directly recover the corresponding secret key. Instead SSA enumerates all possible secret keys (Goppa codes) and then tests permutation equivalence with the public key. The code equivalence problem is not NP-complete. It has been proved to be at least as hard as the graph isomorphism problem [21]. The complexity of SSA-based attack against an Goppa code is approximately binary operations, where . The second attack is without the knowledge of the private key, finding a collision for the given challenge h and it is equivalent to solving GPBD problem by Theorem 1. Hence the proposed chameleon hash scheme is key exposure free.
Mobile 3D assembly process information construction and transfer to the assembly station of complex products
Published in International Journal of Computer Integrated Manufacturing, 2018
Hong Xiao, Yugang Duan, Zhongbo Zhang
Given the currently selected to-be-assembled component , the form features of this component are recognised using the graph-based method (Joshi and Chang 1988), and the AAGs of these form features are a series of subgraphs (pattern graphs) of the AAG corresponding to this component. Finding form features on other components to form assembly features with those form features on component is essentially finding subgraphs that are isomorphic with the pattern graphs in the AAGs (the target graphs) of components . The definition of subgraph isomorphism is given as follows. Given two graphs and , if there is a bijection function such that if and only if , then and are called graph isomorphism, denoted by . If and , then and are called subgraph isomorphism.