Reduções do livro.

Isso é parecido com " Algoritmos do livro ". Embora as reduções também sejam algoritmos, achei duvidoso que se pensasse em uma redução na resposta à pergunta sobre algoritmos do livro. Daí uma consulta separada!

Reduções de todos os tipos são bem-vindas.

Começarei com a redução realmente simples da cobertura de vértices para multicut nas estrelas. A redução quase se sugere assim que o problema de origem é identificado (antes do qual eu acharia difícil acreditar que o problema seria difícil para as estrelas). Essa redução envolve a construção de uma estrela com folhas e a associação de um par de terminais a todas as arestas do gráfico, e é "fácil de ver" que ela funciona. Vou atualizar isso com um link para uma referência, quando eu encontrar um.$n$

Aqueles que estão perdendo o contexto do livro podem querer examinar a pergunta sobre algoritmos do livro .

Atualização: Percebo que não estava totalmente claro o que qualifica como uma redução do livro. Eu acho esse problema um pouco complicado, então confesso que me esquivei deliberadamente do problema deslizando uma referência ao outro segmento :)

Então, deixe-me descrever o que eu tinha em mente e suponho que não é preciso dizer - YMMV a esse respeito. Pretendo uma analogia direta com a intenção original de Provas do Livro. Vi reduções que são terrivelmente inteligentes e me deixo boquiaberto ao ver como essa sequência de pensamentos pode ter ocorrido a alguém. Embora essas reduções me deixem com um senso definido de admiração, esses não são os exemplos que pretendo coletar neste contexto.

O que estou procurando são reduções que são descritas sem muita dificuldade e que talvez sejam levemente surpreendentes, pelo motivo de serem fáceis de entender, mas não fáceis de apresentar. Se você estima que a redução em questão exigirá uma palestra para cobrir, provavelmente ela não se encaixa na conta, embora eu tenha certeza de que pode haver exceções em que a ideia de alto nível é elegante e o diabo está nos detalhes (para o registro, não tenho certeza se consigo pensar em algum).

O exemplo que dei foi deliberadamente simples e, espero, um pouco - se não perfeitamente - ilustrativo dessas características. A primeira vez que ouvi falar sobre corte múltiplo foi em uma sala de aula, e nosso instrutor começou dizendo que não é apenas NP-difícil em geral, é NP-difícil mesmo quando restrito a árvores ... {pausa dramática} de altura um . Lembro-me de não poder provar imediatamente, embora pareça óbvio em retrospecto.

Suponho que óbvio, retrospectivamente, descreva de perto o que estou procurando. Não tenho certeza se isso tem algo a ver com a complexidade da descrição - talvez haja situações em que algo aparentemente obscuro possa ser classificado como elegante - fique à vontade para apresentar seus exemplos (exceções?), Mas eu realmente apreciaria uma justificativa. Dado que, depois de algum momento, isso é uma questão de gosto, você certamente deve se sentir à vontade para encontrar o que considero insanamente complexo, perfeitamente bonito. Estou ansioso para ver uma variedade de exemplos!

Rabin mostra a via de mão única de (x ^ 2 mod N = pq) sem a fatoração de N por uma redução mostrando que se você pode pegar o módulo de raízes quadradas N = pq, então você pode fatorar N.

No aprendizado de máquina, há muitas reduções interessantes. aqui estão alguns exemplos:

• classificação multiclasse a classificação binária ( link ) - pode-se resolver um problema de escolha entre muitas classes, resolvendo problemas mais fáceis de escolher entre duas.
• aprendizado forte a aprendizado fraco ( aumento ) - é possível obter taxas de erro arbitrariamente baixas, dada a capacidade de obter um pouco melhor do que aleatoriamente.
• classificação para classificação ( link )
• perda quadrado a classificação ( sondagem ) - pode-se estimar probabilidades de associação de classe, utilizando um classificador com uma pequena taxa de erro.

Um tutorial de Alina Beygelzimer, John Langford e Bianca Zadrozny aborda alguns outros.

Teorema de Cook-Levin

Qualquer problema no NP pode ser reduzido no polytime por uma máquina determinante de turing para SAT. Para referência, consulte 1 .

Multiplicação de números inteiros para transformar Fourier rapidamente!

Teorema de Rice

Um dos meus favoritos. Reduz o problema de parada a qualquer conjunto de índices (ou é complemento). Veja, por exemplo, Sipser, problema 5.28.

SAT para 3SAT

$k$$k \gt 3$

3SAT a 3COL

Usando gadgets para reduzir o 3SAT ao problema de decidir se um gráfico pode ser colorido com três cores. Para referência, consulte 1 .

No sentido de dizer - oh, isso era simples - em retrospecto:

reduzindo a classificação a um problema convexo do casco.

COBERTURA EXATA POR 3 CONJUNTOS PARA O SUBSET

$U=\{1,2,\ldots,3m\}$$S_1,\ldots,S_n$$U$$m$$U$

$w_1,\ldots,w_n$$K$$K$

$S_i$$\{0,1\}^{3m}$$n+1$$S_i$$w_i=\sum_{j\in S_i} (n+1)^{3m-j}$$K=\sum_{j=0}^{3m-1} (n+1)^j$

(Minha fonte era o livro de Papadimitriou.)