Finalidade de randomização/derandomization básica algoritmo randomizado para MAX SAT

Question

Nas Seções 5.1 do O Design de Algoritmos de Aproximação por Williamson e Shmoys, eles descrevem uma básicas algoritmo randomizado para MAX SENTOU-se e como derandomize-lo.O algoritmo é apenas a atribuir a cada variável de 1 (verdadeiro) com probabilidade 1/2 e 0 (falso) com probabilidade 1/2.Em outras palavras, a amostra uniformemente ao acaso a partir do espaço de todas as soluções.Eles mostram que este é um 1/2 de aproximação.

Em seguida, na Seção 5.2, eles descrevem como derandomize-lo usando o método de condicional expectativas.(Não vou descrever o processo aqui porque ele não é muito complexo e amplamente conhecido, eu estou assumindo.)

A minha pergunta é, por que se preocupar derandomizing desta forma?Ou até mesmo, por que se preocupar em fazer o algoritmo aleatório, em primeiro lugar?

Parece-me que um igualmente bom algoritmo seria o one-liner que de forma determinística define todas as variáveis para 1.Dadas algumas MAX SENTOU-se como instância de entrada, parece-me que você também espera que isso (i.é, "na expectativa de que iria") satisfazer metade das cláusulas.Para mim, a análise do algoritmo aleatório realmente parece dizer que qualquer fixo acho que é "bom". (Em vez de mostrar que o nosso algoritmo aleatório é inerentemente bom.) Então, por que ir através do processo de randomização e derandomizing em primeiro lugar?

Obrigado antecipadamente!

Answer 1

A diferença é que o algoritmo randomizado garante uma esperado 1/2-aproximação em qualquer entrada.Por outro lado, é fácil para um adversário para a construção de uma entrada (i.e.uma instância do MAX-SAT) para que o determinista "definir as variáveis para as verdadeiras" algoritmo satisifes zero cláusulas.

Lembre-se de que o exemplo de espaço para um estudo randomizado algoritmo é através de um conjunto de auxiliar de bits aleatórios.Não há distribuição de probabilidade assumidas, sobre o entradas.O típico objetivo do algoritmo randomizado de design é, para cada entrada a ser bem tratadas, na expectativa.(Algoritmo de análise de comportamento sobre uma suposta distribuição de entrada é chamado de média-análise de caso em vez disso.)

O que são auxiliares bits aleatórios?

Suponha que nós temos um estudo randomizado máquina de Turing $M_1$ que é executado em instâncias de comprimento $n$ por não mais do que $T(n)$ tempo, durante o qual ele não faz mais do que R $(n) \le T(n)$ decisões aleatórias.Podemos transformar a máquina em um determinista Máquina de Turing $M_2$ que tem duas fitas de entrada:o costume de fita que contém a seqüência de caracteres de entrada $x$ de comprimento $n$, e uma fita que contém uma seqüência de caracteres $r$ de comprimento R $(n)$.A seqüência de caracteres $r$ é a nossa cadeia de auxiliar de bits aleatórios;ele determina que "por acaso" as decisões a máquina de Turing é fazer.Quando dizemos que a randomizados máquina de Turing executar $M_1(x)$ aceita com probabilidade $p$, isso é equivalente a dizer que o conjunto $$A(x) = \left\{r\ |\ r \in \{0, 1\}^{R(|x|)}, M_2(x, r) ext{ aceita} ight\}$$ de $r$ cadeias de caracteres que fazer $M_2(x, r)$ aceitar constitui uma fração $p = |Um(x)| / 2^{|x|}$ do conjunto de todos os $r$ cadeias de caracteres.

Você pode reconhecer o que está acontecendo aqui, se você já viu a construção análoga para máquinas de Turing não-determinísticas.Podemos pensar em um NP máquina como um não-determinísticos máquina que os ramos em exponencialmente várias cópias de si mesmo.Mas também podemos pensar nele como um determinista o verificador de máquina que requer uma entrada e uma "prova" de cadeia, com os critérios de aceitação que uma seqüência de caracteres de entrada é na linguagem que se qualquer cadeia de caracteres de prova faz com que a máquina aceita.

Muitas vezes é mais fácil pensar sobre esse baixo-à-Terra conceito de determinista verificador de máquinas e o subconjunto de prova de cadeias de caracteres faz com que a máquina aceita em um dado de entrada, ao invés de pensar sobre idéias abstratas, como exponencialmente ramos de máquinas e mundos possíveis.E torna-se mais fácil para definir a complexidade de classes, tais como a co-NP, PP, BPP, ⊕P, etc., todos os que são, essencialmente, "NP com uma aceitação diferentes regra." Por exemplo:

• NP é o conjunto de idiomas $L$ para o qual existe um verificador polinomial máquina $M_2$ de tal forma que $x \in$L se, e somente se, existe uma $r$ seqüência de caracteres tais que $M_2(x, r)$ aceita (onde o comprimento do $r$ seqüência de caracteres é limitado por um polinˆ omio R $(|x|)$).
• BPP é o conjunto de idiomas $L$ para o qual existe um verificador polinomial máquina $M_2(x, r)$ de tal forma que $x \in$L implica que $M_2(x, r)$ aceita, pelo menos ⅔ de $r$ cadeias de caracteres e $x otin L$ implica que $M_2(x, r)$ aceita para mais de ⅓ $r$ cadeias de caracteres (onde o comprimento do $r$ cadeias de caracteres é limitado por um polinˆ omio R $(|x|)$).

Nota:Na maioria das vezes, não importa se nós exigimos que o $r$ seqüências de comprimento exatamente R $(n)$ ou no mais R $(n)$, desde permitindo cordas mais curtas, apenas aumenta o número de possíveis seqüências de caracteres por um fator constante.