Dispersor

A dispersão é um extrator unilateral. Quando um extrator exige que cada evento recebe a mesma probabilidade sob a distribuição uniforme e a distribuição extraída, apenas o último é necessário para um dispersor. Então para um dispersor, um evento A⊆ ⊆ (0,1?m{displaystyle Asubseteq {0,1}^{m}} nós temos: 1-epsilon }" xmlns="http://www.w3.org/1998/Math/MathML">PRUmNão.A]>1- Sim. - Sim. ε ε Não. Pr_{U_{m}}[A]>1-epsilon }1-epsilon " aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/db07f7af85ad63077cb27053d3e712ee7982e5bd" style="vertical-align: -0.838ex; width:16.567ex; height:2.843ex;"/>

Definição (Disperser): A (k,ε ε )(k,epsilon)}- Disperser é uma função

DEu...S:(0,1?n× × (0,1?D→ → (0,1?mNão. Dis:{0,1}^{n}times {0,1}^{d}rightarrow {0,1}^{m}}

tal que para cada distribuição X- Sim. sobre (0,1?n{displaystyle {0,1}^{n}} com H. H. H.∞ ∞ (X)≥ ≥ k(X)geq k} o apoio da distribuição DEu...S(X,UD)Não. Dis(X,U_{d})} é de tamanho pelo menos (1- Sim. - Sim. ε ε )2m{displaystyle (1-epsilon)2^{m}}.

Teoria dos gráficos

An (N, M, D, K, e)-disperser é um grafo bipartido com N vértices no lado esquerdo, cada um com grau D e vértices M no lado direito, de modo que cada subconjunto de vértices K no lado esquerdo esteja conectado a mais de (1 − e)M vértices o certo.

Um extrator é um tipo de gráfico relacionado que garante uma propriedade ainda mais forte; cada (N, M, D, K, e) -extractor também é um (N, M, D, K, e)-dispersor.

Outros significados

Um dispersor é um dispositivo de mistura de alta velocidade usado para dispersar ou dissolver pigmentos e outros sólidos em um líquido.