Algorítmica y complejidad computacional. Varios enlaces.

1. Hablando de Arxiv, ayer se colgó en esta plataforma un nuevo paper que parece interesante y que debo de leer con más detenimiento (aunque por la falta de costumbre cada vez me cuesta más leer sobre estos temas).

Título. Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

Abstract.

We show that derandomizing polynomial identity testing over an arbitrary finite field implies that NEXP does not have polynomial size boolean circuits. In other words, for any finite field F(q) of size q, PITq ∈ NSUBEXP ⇒ NEXP !⊆ P/poly, where PITq is the polynomial identity testing problem over F(q), and NSUBEXP is the nondeterministic subexpoential time class of languages. Our result is in contract to Kabanets and Impagliazzo’s existing theorem that derandomizing the polynomial identity testing in the integer ring Z implies that NEXP does have polynomial size boolean circuits or permanent over Z does not have polynomial size arithmetic circuits

Enlace.  

Este resultado tiene que ver con las clases BPP, NEXP y P/poly y sus relaciones.

Algunos artículos sobre este tema aquí y aquí entre otros.

BPP es el equivalente de P pero en versión aleatoria.

P/Poly es una clase que nunca había conocido en detalle y por eso estoy empezando a estudiarla en los ratos libres. Para unos primeros datos sobre esta clase P/Poly puedes ver 12. Es una clase con dos definiciones alternativas eqivalentes. Una está basada en circuitos. Sobre circuitos en general recordemos que todo circuito es equivalente a uno sin constantes en los nodos inputs (es decir todos estos serían variables). Como es sabido hay familias de circuitos no uniformes y familias de circuitos uniformes (que son aquellos constructibles por una Máquina de Turing (por un algoritmo). Es importante señalar que las segundas no pueden  reconocer lenguajes indecidibles. Como veremos las primeros, las no uniformes sí.  La otra definición de P/poly está basada en Máquinas de Turing de tiempo polinómico, pero con un dato adicional al input,  un consejo (advice) cuyo tamaño se calcula en función del tamaño del input (del problema) y cuyo tiempo y/o espacio de computación no tiene restricciones (es decir se podría obtener el consejo tras una computación de tiempo exponencial). Para el esbozo de una demostración de por qué son equivalentes se puede ver esta página de wikipedia (extracto: One direction of the equivalence is easy to see (se refiere a la dirección–>circuitos máquina). If, for every n, there is a polynomial size Boolean circuit A(n) deciding the problem, we can use a Turing machine that interprets the advice string as a description of the circuit. Then, given the description of A(n) as the advice, the machine will correctly decide the problem on all inputs of length n. The other direction (es decir máquina –> circuito) uses a simulation of a polynomial-time Turing machine by a polynomial-size circuit as in one proof of Cook’s Theorem. Simulating a Turing machine with advice is no more complicated than simulating an ordinary machine, since the advice string can be incorporated into the circuit).

Sobre P/poly primeros señalemos que por una parte ni  P/poly (ni P/log) pueden estar incluidos en NP ya que son clases basadas en circuitos y no en Máquinas de Turing (MT). Como es sabido una MT sirve para inputs de todos los tamaños. Es uniforme; se puede describir de manera finita pero puede aceptar un número infinito de cadenas o strings. Pero un circuito sólo sirve para inputs de un solo tamaño; digamos, cada circuito de una familia infinita, sólo puede procesar cadenas de n símbolos. Por lo tanto no es un sólo circuito el que se corresponde con una máquina o puede aceptar un lenguaje, sino una familia de circuitos, una para cada tamaño de input o cadena. Una familia de circuitos es no-uniforme; puede implicar una descripción infinita.  Cómo es sabido la clase P/Poly incluye a Tally (la clase de lenguajes unarios). Para todo lenguaje L de la clase Tally existe una familia de circuitos que lo reconoce. Cómo consecuencia, dado que hay lenguajes unarios o Tally indecidibles (es decir tal que no puede existir un algoritmo, para una definición formal de este concepto, que lo reconozca), hay familias de circuitos en P/poly que reconocen lenguajes indecidibles. También es conocido que SPARSE contains TALLY, the class of unary languages, since these have at most one string of any one length. Although not all languages in P/poly are sparse, there is a polynomial-time Turing reduction from any language in P/poly to a sparse language.  (Nota: Parte de este párrafo es traducción libre de las páginas 181 y 182 de este libro de 2011 titulado Computability and Complexity Theory de Homer y Selman; parte de esta entrada de wikipedia y de este paper citado en ella).

Por otra parte P/poly en cierto modo es más limitada que NP ya que utiliza el mismo consejo (advice) para todos los inputs de un mismo tamaño, sin embargo en NP inputs del mismo tamaño pueden utilizar consejos diferentes (los así llamados certificados de soluciones).

Teniendo en cuenta estos dos aspectos y el hecho de que NEXP podría estar incluida en P/poly, surge la pregunta sobre en que clase más amplia está incluida esta última. Sobre esto es sobre lo que precisamente hablan en este paper titulado Locating P/poly optimally in the extended low hierarchy. Es decir P/poly está en uno de los niveles (concretamente en el nivel EL3^p,Omega).

Sobre NEXP hemos hablado en extenso en este blog y en base a estas consideraciones pensamos de una manera muy concreta con respecto a su relación con EXP. Sobre la relación de NEXP y BPP, no creo haber sabido nunca (pero llevo más de un año sin leer sobre estos asuntos y los tengo completamente oxidados, con  lo cual es posible que esté equivocado) que todavía no está excluido que BPP=NEXP. Esto es para mi chocante. Relacionado con esto anterior se conoce el teorema de Adelman según el cual BPP sí está incluido en P/Poly. Pero si NEXP estuviese incluido en P/Poly entonces NEXPTIME=EXPTIME. ¿ Y la inversa ?

¿ Confuso ? Sí, para mi también. Hmm…a ver si en navidades me aclaro sobre todo esto.

2. También se ha colgado recientemente una pregunta curiosa en TCS Stack Exchange sobre algoritmos.

Es una pregunta que mucha gente se habrá planteado muchas veces: ¿ que algoritmos han tenido tanto éxito desde el punto de vista de sus usos prácticos que se puedan poner como ejemplo de esto en cenas de amiguetes y clases de universidad ? (yo la que me hago es cuales han tenido éxito desde el  punto de vista comercial…).

Hay algunos ejemplos clásicos cómo Simplex o FFT. Hablan de otro sobre el que hemos hablado en el blog precisamente en un contexto muy relacionado con la pregunta.

Pese a que ha habido múltiples respuestas, parece que la persona que ha planteado la pregunta finalmente no ha quedado satisfecha. Por ello, si puedes aportar algún otro ejemplo, adelante.

3. Un investigador ha esbozado una posible estrategia de ataque para el Problema fundamental de complejidad computacional (al menos convencionalmente) y está pidiendo opiniones y proponiendo, si estas son favorables, un ataque colectivo de tipo Polymath.  Ni he leído la estrategia propuesta ni sé si está consiguiendo colaboradores, pero parece una noticia digna de reseñar. Igual en navidades, con las vacaciones, se anima este asunto.

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: