l este artículo está sobre el extractor en matemáticas, porque el otro uso de esta palabra considera: Extractor (armas de fuego) .

Un $(,\; \backslash \; épsilon\; de\; N,\; de\; M,\; de\; D,\; de\; K)$ - el extractor es un gráfico bipartito con nodos de $N$ a la izquierda y nodos de $M$ a la derecha tales que cada nodo a la izquierda tiene vecinos de $D$ (a la derecha), que tiene la característica agregada eso para cualquier subconjunto $A$ de las cimas izquierdas del tamaño por lo menos $K$, la distribución en las cimas correctas obtenidas eligiendo un nodo al azar en $A$ y entonces después de un borde al azar para conseguir un nodo x en el derecho es el $\backslash \; epsilon$-close a la distribución del uniforme en términos de distancia de la variación total.

Un dispersor es un gráfico relacionado.

Una manera equivalente de ver un extractor está como función de dos variables

$E\; :\; \backslash \; épocas\; \backslash \; rightarrow$

de la manera natural. Con esta visión resulta que la característica del extractor es equivalente a: para cualquier fuente de aleatoriedad $X$ que dé los pedacitos de $n$ con el $\backslash \; el\; registro\; K$ de la Minuto-entropía, el $E\; (X,\; U\_D)\; de\; la\; distribución$ es el $\backslash \; epsilon$-close a $U\_M$, donde $U\_T$ denota la distribución uniforme en $$.

Los extractores son interesantes cuando pueden ser construidos con el pequeño $K,\; \backslash \; epsilon$ $N$ en relación con de D y $M$ está tan cerca a $KD$ (la aleatoriedad total en las fuentes de entrada) como sea posible.

Las funciones del extractor fueron investigadas original como manera a la aleatoriedad del extracto del de fuentes débil al azar.

Usar el método de probabilidad es fácil demostrar que existen los gráficos del extractor con parámetros realmente buenos. El desafío es encontrar los ejemplos computables polinómicos explícitos o del tiempo de tales gráficos con buenos parámetros. Los algoritmos que computan gráficos del extractor (y dispersor) han encontrado muchos usos en el de informática.