Reductions in computational complexity using Clifford algebrasReportar como inadecuado

Reductions in computational complexity using Clifford algebras - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 IECN - Institut Élie Cartan de Nancy 2 TRIO - Real time and interoperability INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications 3 Department of Mathematics and Statistics - Southern Illinois University

Abstract : A number of combinatorial problems are treated using properties of abelian nilpotent- and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of $\Lambda^k$, where $\Lambda$ is an appropriate nilpotent adjacency matrix, the $k$-cycles in any finite graph are recovered. Within the algebra context i.e., considering the number of multiplications performed within the algebra, these problems are reduced to matrix multiplication, which is in complexity class $P$. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and $\sharp P$-complete to class $P$ in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.

Keywords : Hamiltonian cycles traveling seesman problem longest path NP-hard NP-complete cycle over set packing problem set covering problem matrix permanent quantum computing

Autor: René Schott - Stacey Staples -



Documentos relacionados