Complejidad computacional. Enlaces varios edición julio 2014..

Una compilación de enlaces sobre Complejidad Computacional que hice hace tiempo y publico ahora.

I. NPI. 

Los problemas clásicos o más conocidos en esta clase  son: Isomorfismo de grafos y similares, factorización de enteros y logaritmo discreto. Pero hay más:

1. Una lista bastante completa de problemas NPI.

Viendo está lista no está tan claro que los problemas NPI sean tan escasos como se pensaba.

Esto es precisamente lo que intentan aclarar en esta otra pregunta de CS Stack Exchange.

2. Algunos problemas NPI que no conocía.

Extraidos de la lista anterior y que no conocía.

2.1. Isomorfismo de anillos.

El paper dónde demuestran sus propiedades desde el punto de vista de la complejidad computacional.

Lo que vienen a decir es que Isomorfismo de grafos es reducible  en isomorfismo de anillos pero la conversa no se ha demostrado. Lo mismo pasa con isomorfismo de grupos, reducible a isomorfismo de grafos aunque la conversa no se conoce que sea cierta.

2.2 Un problema: Assuming EXP !=NEXP Padded versions of NEXP-complete problems.

¿ Que es padding ? La respuesta aquí. Y una entrada relacionada con esta cuestión en TCSSE.

I think the best way to get intuition for this issue is to think of what the complete problems for exponential time classes are. For example, the complete problems for NE are the standard NP-complete problems on succinctly describable inputs, e.g., given a circuit that describes the adjacency matrix of a graph, is the graph 3-colorable? Then the problem of whether E=NE becomes equivalent to whether NP problems are solvable in polynomial time on the succinctly describable inputs, e.g., those with small effective Kolmogorov complexity. This is obviously no stronger than whether they are solvable on all inputs. The larger the time bound, the smaller the Kolmogorov complexity of the relevant inputs, so collapses for larger time bounds are in effect algorithms that work on smaller subsets of inputs.

2.3 Deciding Whether a Graph Admits a Graceful Labeling

3. Reducciones entre problemas NPI.

Una de las propiedades de los problemas NPI es que se piensa que no son reducibles unos a otros en tiempo polinómico, a diferencia de lo que pasa con los problemas NP-completos (dónde si existen este tipo de reducciones). Esto es una característica todavía inexplicada. En la respuesta a una pregunta en TCSSE sobre esto intentan dar alguna explicación.

II. SUBEXP.

Una pregunta de nuestro interés sobre esta clase, de nuevo en TCSSE.

III. ETH.

Sobre la posibilidad de algoritmos  más rápidos para SAT.

IV. Complejidad computacional y teoría de grupos. 

Título. A FAMILY OF POLYCYCLIC GROUPS OVER WHICH THE CONJUGACY PROBLEM IS NP-COMPLETE .

Uno de los autores del artículo es también autor del un libro titulado Computational and Combinatorial Group Theory and Cryptography.

IV. Energy efficient computation.

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: