Algorítmica y complejidad computacional. HAMILTON CYCLE PROBLEM THROUGH GRASSMANN NUMBERS.

Hago una entrada específica sobre un apartado de un artículo que he visto hoy en arxiv, que  parece interesante pero sobre el que, tras una primera lectura en diagonal, no he entendido nada. Pero nada nada, lo cual me preocupa :-(.

Como me tengo que poner las pilas sobre estos temas  de nuevo, temas que tengo completamente oxidados, es una buena ocasión para comenzar…Lo siento lector, pero voy a empezar a publicar bastante más sobre estos temas.

Título. P=?NP as minimization of degree 4 polynomial, or Grassmann number problem

AbstractWhile the P vs NP problem is mainly being attacked form the point of view of discrete mathematics, this paper propses two reformulations into the field of abstract algebra and of continuous global optimization – which advanced tools might bring new perspectives and approaches to attack this problem. The first one is equivalence of satisfying the 3-SAT problem with the question of reaching zero of a nonnegative degree 4 multivariate polynomial. This continuous search between boolean 0 and 1 values could be attacked using methods of global optimization, suggesting exponential growth of the number of local minima, what might be also a crucial issue for example for adiabatic quantum computers. The second discussed approach is using anti-commuting Grassmann numbers θ i, making ( A · diag ( θ i)) n nonzero only if A has a Hamilton cycle. Hence, the P 6=NP assumption implies exponential growth of matrix representation of Grassmann numbers.

En principio no es más que otro paper con una reducción de 3-sat a otros problemas compleidad-computacionalmente equivalentes.

La novedad es que estos otros problemas no son de matemática discreta (al menos uno de ellos; no lo tengo claro con respecto al otro).

Además me ha llamado la atención por un par de temas. Lo publico en el blog para que no se me olvide. Aparentemente, y el mismo autor lo reconoce, atacar el problema de recorridos hamiltonianos por esta vía es matar moscas a cañonazos (el problema es exactamente el mismo que resolver el problema en Digrafos de Cayley teniendo que construir todo el digrafo).

Se pone de manifiesto un vez más lo que ya sabe todo el mundo pero no se si  está incluido en las teorías: un algoritmo consta  al menos de tres partes o fases: la fase de representación del input, la fase de búsqueda de solución (que es lo que normalmente se llama algoritmo) y la fase de expresión o representación de la solución (usualmente llamada output, pero que en realidad es la prueba de la solución, que puede adoptar muchas formas diferentes, unas más largas que otras), y la fase de comunicación de la  solución a una tercera parte.

¿ Tiene sentido considerar esta cuarta fase como diferente a la tercera ?. Dos casos: comunicación de la computadora al ser humano una vez ha obtenido el resultado; o lo mismo de ser humano a ser humano. En el fondo la pregunta es si se puede  optmizar, hacer más sucinto un output, la prueba de una solución, una vez que se conoce la solución en una de sus formas. Ejemplo concreto: obtengo un recorrido hamiltoniano; hay alguna manera de procesar esta solución de tal modo que obtenga una prueba más corta que mostrar la secuencia de vértices ?).  Me temo que no estoy expresando la idea claramente y eso significa que no la tengo clara.

La  contabilidad de complejidad computacional debe de tener  en cuenta el  coste en todas las fases, debe de haber un computo global.

Por otra parte le estoy dando vueltas a un tema desde hace tiempo: al igual que existe la idea de equivalencia de problemas computacionales (mediante reducciones), que está relacionada con las fases de representación del input y del  output, ¿ no existirá una manera de demostrar que dos algoritmos, en su fase de búsqueda de solución ?. Si no el  concepto de algoritmo (fase de búsqueda de solución) queda demasiado abierto. Está el concepto de simulación de un proceso por otro, pero no se si esto se ha bajado a la tierra e integrado en la teoría de complejidad  computacional.

Volviendo al artículo, aunque  utiliza los números de Grassman, y estos se utilizan en alguna rama de la física, el artículo no tiene ninguna relación con la física (según estoy viendo).

Relacionado.  Números de Grassman.

http://www.scienceforums.net/topic/83928-grassman-variables-for-hamilton-cycle-problem/

http://www.sciforums.com/threads/grassman-variables-for-hamilton-cycle-problem.141963/

Para situar las Algebras de Grassman (o Algebra Exterior) en un contexto  más general (no se necesita todo esto para comprender el paper sobre el que hablamos pero me ha picado la curiosidad).

http://math.stackexchange.com/questions/667830/modern-research-into-grassmans-theory-of-forms

https://en.wikipedia.org/wiki/Hypercomplex_number

Todo esto entra dentro de campo de las algebras asociativas. Recuerdo que cuando me apasionaban estos temas compré un libro sobre algebras no asociativas…¡¡ y lo leí !!. A ver si lo recupero para ampliar el contexto. Recuperado: es del de Schafer de 1966.

Algunos nombres conocidos, como Hamilton y Cayley y otros nuevos como Cockle (en relación a las teserinas,  que tampoco conocía).

El artículo de Rota en el que sitúa el trabajo de Grassman en su verdadero  contexto.

http://kalx.net/dsS2011/BarBriRot1985.pdf

Un extracto que me ha llamado la atención (un deja vu)

Unlike the symmetric algebra, the exterior algebra of a finite-dimensional vector space is isomorphic to its dual as a Hopf algebra. This isomorphism is ill-matched with the asymmetry of interior products. It can be expressed by remarking that interior products in exterior algebra satisfy additional identities not shared by interior products of the symmetric algebra. At bottom, the key fact is that the determinant of the product of two matrices equals the product of the determinants, while no such property holds for the permanent.

Anuncios

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: