Complejidad computacional. Decidir, buscar, muestrear y contar.

En la anterior entrada sobre las “máquinas QBSM” me he dado cuenta que no tengo muy clara la teoría de complejidad del muestreo que continuamente aparece en cuestiones vinculadas a la computación cuántica.

Repasamos primero los problemas “clásicos” de decisión, conteo y búsqueda  que han centrado la atención teoría de la complejidad computacional y por todos conocidos🙂, y, tras un breve interludio sobre el problema del permanente (relacionado con las máquinas QBSM), a continuación nos centramos en la teoría de complejidad propia del muestreo, básicamente indicando alguna literatura relevante.

1. Decisión , búsqueda y conteo. 

Los problemas de existencia-decisión sobre lenguajes, a los que asociamos las clases de complejidad de decisión, las más conocidas por todos, son los aquellos que responden a preguntas sobre existencia de solución y cuya respuesta es en forma sí o no.

Hay otra clase de problemas, los problemas de construcción-búsqueda, también llamados funcionales, que no se conforman con afirmaciones existenciales (basadas en demostraciones existenciales o constructivas) sino que piden construir una solución en concreto y para los que se han desarrollado clases de complejidad propias. Esta solución constructiva puede ser una cualquiera y puede variar en función del problema (para algunos problemas la solución es un número; en otros casos la solución es un objeto combinatorio) o puede ser una solución sometida a restricciones adicionales en cuyo caso estaríamos ante problemas de optimización. Cuando la solución pedida es cuantitativa/numérica, nos podemos conformar con una aproximación y por lo tanto hablaríamos de problemas de aproximación.

Finalmente los problemas de cuantificar-conteo son aquellos que responden a preguntas sobre número de soluciones de un problema y en cierta manera se reducen a contar el número de “síes”.   Por eso están de alguna manera relacionados con los problemas de decisión. También en este caso,  a veces podemos o debemos conformarnos con una mera aproximación del número de soluciones.

Habiendo definido clases de complejidad para estos diferentes problemas es importante preguntarse que relación existe entre estos tipos de clases de complejidad. Por ejemplo entre decisión y búsqueda. O entre decisión y conteo. O entre optimización y conteo.

2. Permanente.

El permanente es un problema interesante ya que se puede definir tanto cómo un problema de búsqueda (dada una matriz, encontrar el valor del permanente, según su definición algebraica; la reducción a matrices 0-1 conserva la complejidad, es decir el problema no es más fácil para este tipo de matrices) cómo de conteo (por ejemplo dado un grafo encontrar el numero de emparejamientos perfectos o el número de vertex cycle cover; estos dos problemas son el mismo que computar la permanente de una matriz 0-1, la matriz que representa al grafo).

Todo esto se puede ilustrar fácilmente con la siguiente proposición:

Thus, if the permanent can be computed in polynomial time by any method, then FP = #P, which is an even stronger statement than P = NP

(Nota al margen. Muy interesante: The problems of finding a vertex disjoint and edge disjoint cycle covers with minimal number of cycles are NP-complete. The problems are not in complexity class APX. The variants for digraphs are not in APX either.[2]). 

3. Muestreo.

Una cuarta categoría de problemas, son los llamados problemas de muestreo o sampling problems (en general muestreo uniforme, es decir que cada posible solución tenga la misma probabilidad en cuyo caso también se llaman problemas de generación uniforme). A continuación algunos artículos antiguos y recientes sobre esto:

–1976. The complexity of nonuniform random number generation, de Knuth y Yao. Por lo visto este paper inicia la relación de la algorítmica de generación de números aleatorios con la teoría de complejidad. No he podido encontrar una copia accesible.

–1986. Random generation of combinatorial structures from a uniform distribution.

Abstract.

The class of problems involving the random generation of combinatorial structures from a uniform distribution is considered. Uniform generation problems are, in computational difficulty, intermediate between classical existence and counting problems.

It is shown that exactly uniform generation of ‘efficiently verifiable’ combinatorial structures is reducible to approximate counting (and hence, is within the third level of the polynomial hierarchy).

Natural combinatorial problems are presented which exhibit complexity gaps between their existence and generation, and between their generation and counting versions. It is further shown that for self-reducible problems, almost uniform generation and randomized approximate counting are inter-reducible, and hence, of similar complexity.

Extracto. 

To each relation of the above form, there correspond a number ofnaturaUy
defined problems, the classical ones being existence, construction, and counting. This paper introduces a fourth kind, namely uniform generation, and investigates its relationship with the classical problem classes.

A formal definition of the four problem classes is given below, each definition being followed, in parentheses, by the interpretation of the problem in the paradigmatic case of the 1-factor relation. Throughout, x element of E represents a problem instance.

(1) Existence: Does there exist a word y element of E such that xRy? (does the graph G contain a 1-factor?)

(2) Construction: Exhibit a word y element of E satisfying xRy, if such exists.( construct a 1-factor of G.)

(3) (Uniform) Generation: Generate uniformly, at random, a word y element of E satisfying xRy. (generate, at random, a 1-factor of the graph G. Each 1-factor is to appear with equal probability.)

(4) Counting: How many words y element of E satisfy xRy? (How many 1-factors does G possess?)

En este paper se origina, por lo visto, la literatura sobre complejidad computacional del muestro. Su principal contribución es aportar evidencias de que (entiendo que lo que sigue es sólo para problemas en NP; tengo que comprobarlo):

problemas de existencia <= problemas de construcción <= problemas de generación uniforme <= problemas de conteo

y que los problemas de generación uniforme exacta se pueden reducir a los problemas de conteo aproximado.

(Nota al margen. Interesante paper: Monte-Carlo approximation algorithms for enumeration problems:

We develop polynomial time Monte-Carlo algorithms which produce good approximate solutions to enumeration problems for which it is known that the computation of the exact solution is very hard. We start by developing a Monte-Carlo approximation algorithm for the DNF counting problem, which is the problem of counting the number of satisfying truth assignments to a formula in disjunctive normal form. The input to the algorithm is the formula and two parameters ε and δ. The algorithm produces an estimate which is between 1 − ϵ and 1 + ϵ times the number of satisfying truth assignments with probability at least 1 − δ. The running time of the algorithm is linear in the length of the formula times View the MathML source times View the MathML source.

On the other hand, the problem of computing the exact answer for the DNF counting problem is known to be #P-complete, which implies that there is no polynomial time algorithm for the exact solution if P ≠ NP. This paper improves and gives new applications of some of the work previously reported. Variants of an ϵ, δ approximation algorithm for the DNF counting problem have been highly tailored to be especially efficient for the network reliability problems to which they are applied. In this paper the emphasis is on the development and analysis of a much more efficient ϵ, δ approximation algorithm for the DNF counting problem. The running time of the algorithm presented here substantially improves the running time of versions of this algorithm given previously. We give a new application of the algorithm to a problem which is relevant to physical chemistry and statistical physics. The resulting ϵ, δ approximation algorithm is substantially faster than the fastest known deterministic solution for the problem).

–2012. The complexity of distributions y una tesis de 2013 del mismo autor The Computational complexity of Randomness. Creo que esta tesis es exactamente lo que estábamos buscando.

Extracto de la tesis.

This dissertation explores the multifaceted interplay between ecient computation and probability distributions. We organize the aspects of this interplay according to whether the randomness occurs primarily at the level of the problem or the level of the algorithm, and orthogonally according to whether the output is random or the input is random.

Part I concerns settings where the problem’s output is random. A sampling problem associates to each input x a probability distribution D(x), and the goal is to output a sample from D(x) (or at least get statistically close) when given x. Although sampling algorithms are fundamental tools in statistical physics, combinatorial optimization, and cryptography, and algorithms for a wide variety of sampling problems have been discovered, there has been comparatively little research viewing sampling through the lens of computational complexity.  We contribute to the understanding of the power and limitations of efficient sampling by proving a time hierarchy theorem which shows, roughly, that “a little more time gives a lot more power to sampling algorithms.” 

Esta primera parte trata precisamente del tema que nos interesa y tras una lectura en diagonal sigo sin tener muy claro de momento de que va.

Part II concerns settings where the algorithm’s output is random. Even when the specification of a computational problem involves no randomness, one can still consider randomized algorithms that produce a correct output with high probability. A basic question is whether one can derandomize algorithms, i.e., reduce or eliminate their dependence on randomness without incurring much loss in eciency. Although derandomizing arbitrary time-efficient algorithms can only be done assuming unproven complexity-theoretic conjectures, it is possible to unconditionally construct derandomization tools called pseudorandom generators for restricted classes of algorithms. We give an improved pseudorandom generator for a new class, which we call combinatorial checkerboards. The notion of pseudorandomness shows up in many contexts besides derandomization. The so-called Dense Model Theorem, which has its roots in the famous theorem of Green and Tao that the primes contain arbitrarily long arithmetic progressions, is a result about pseudorandomness that has turned out to be a useful tool in computational complexity and cryptography. At the heart of this theorem 1 is a certain type of reduction, and in this dissertation we prove a strong lower bound on the advice complexity of such reductions, which is analogous to a list size lower bound for list-decoding of error-correcting codes.

Esta segunda parte trata de algoritmos probabilísticos o aleatorios (Las Vegas  ¿ Alcorcón :-?), Montecarlo,  etc…) y su desaleatorización (Randomness can be viewed as a resource, like space and time. Derandomization is then the process of removing randomness (or using as little of it as possible). From the viewpoint of computational complexity, derandomizing an efficient randomized algorithm is the question, is P = BPP ?)

Part III concerns settings where the problem’s input is random. We focus on the topic of randomness extraction, which is the problem of transforming a sample from a high-entropy but non-uniform probability distribution (that represents an imperfect physical source of randomness) into a uniformly distributed sample (which would then be suitable for use by a randomized algorithm). It is natural to model the input distribution as being sampled by an ecient algorithm (since randomness is generated by ecient processes in nature), and we give a construction of an extractor for the case where the input distribution’s sampler is extremely ecient in parallel time. A related problem is to estimate the min-entropy (“amount of randomness”) of a given parallel-time-ecient sampler, since this dictates how many uniformly random output bits one could hope to extract from it. We characterize the complexity of this problem, showing that it is “slightly harder than NP-complete.”

Esta parte habla de extractores (extractors) de aleatoriedad. Es decir de cómo extraer de una fuente aleatoria sesgada un corriente de información aleatoria no sesgada.

Part IV concerns settings where the algorithm’s input is random. Average-case complexity is the study of the power of algorithms that are allowed to fail with small probability over a randomly chosen input. This topic is motivated by cryptography and by modeling heuristics. A fundamental open question is whether the average-case hardness of NP is implied by the worst-case hardness of NP. We exhibit a new barrier to showing this implication, by proving that a certain general technique (namely, “relativizing proofs by reduction”) cannot be used. We also prove results on hardness amplification, clarifying the quantitative relationship between the running time of an algorithm and the probability of failure over a random input (both of which are desirable to minimize).

Esta cuarta parte trata de la teoría de complejidad del caso medio o average case complexity, sobre la que ya hemos hablado largo y tendido en este blog hace ya bastante tiempo.

–2012. Time hierarchies for sampling distributions.

–2012. Large deviation bounds for decision trees and sampling lower bounds for AC0. (presentación con una interesante introducción histórica;  también existe en formato de artículo).

–2010. The equivalence of sampling and searching. De un autor ya bastante conocido en este blog.  Lo puedes encontrar también en formato de presentación.

Extracto:  

Many researchers observed that just because a function F is hard doesn’t mean that (x, F(x)) x∈{0,1}^n  is hard to sample uniformly.

– Even when f = integer factorization, we can
sample this in polynomial time [Bach’85, Kalai]

– Even when f = parity, we can still sample this
distribution in AC0. [Babai’87, Boppana Lagarias ‘87]

Cómo se ve si bien la algorítmica del muestro en ciencias computacionales (método MCMC) y la teoría de complejidad del muestro aleatorio de estructuras combinatorias tienen ya bastante solera, la literatura sobre cotas inferiores es bastante nueva. Y aunque he trabajado en temas de muestreo aleatorio, (antes de leer estos papers) sigo sin tener muy claro de que va todo este tema. Pero el extracto anterior aclara otra duda que nos planteábamos hace dos entradas.

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: