P vs NP: exemplo instrutivo de quando a busca por força bruta pode ser evitada

8

Para poder explicar o problema P vs NP a não matemáticos, eu gostaria de ter um exemplo pedagógico de quando a busca por força bruta pode ser evitada. Idealmente, o problema deve ser imediatamente compreensível e o truque não deve ser muito fácil nem muito difícil.

O melhor que eu vim até agora é

SUBSET_PRODUCT_IS_ZERO

O problema é fácil de entender (dado um conjunto de números inteiros, um subconjunto com o produto 0 pode ser formado?), Mas o truque é muito fácil (verifique se 0 está entre os números fornecidos, ou seja, não é necessário examinar muitos subconjuntos).

Alguma sugestão?

sixpanbass
fonte
Deseja um algoritmo melhor que o de força bruta para um problema NP-completo ou para um problema bobo, como subconjunto-produto-é-0? Que tal o truque que faz para soma de subconjuntos, veja, por exemplo, o algoritmo horowitz e sahni aqui rjlipton.wordpress.com/2010/02/05/…2n/2+o(n)
Sasho Nikolov
Talvez eu não tenha entendido bem a pergunta, mas se você precisar de um problema facilmente compreensível em P com um algoritmo de tempo polinomial de "nível intermediário", sugiro a satisfação clássica do 2-CNF .
Marzio De Biasi
4
Que tal 2-Coloring vs 3-Coloring?
Serge Gaspers
6
A maneira como esta pergunta é escrita parece pressupor que problemas completos de NP só podem ser resolvidos por busca de força bruta. Isso seria um erro. Por exemplo, a busca ingênua de força bruta pelo problema do vendedor ambulante leva tempo Enquanto pode ser resolvida por um algoritmo de programação dinâmica sem força bruta no tempo muito mais rápido . O ( n 2 2 n )O(n!)O(n22n)
David Eppstein

Respostas:

22

Eu recomendo Jenga !

Supondo que você tenha dois jogadores perfeitamente lógicos, sóbrios e hábeis, o Jenga é um jogo para dois jogadores com informações perfeitas, como Damas ou Go. Suponha que o jogo comece com uma pilha de tijolos , com 3 tijolos em cada nível. Na maior parte do jogo, cada jogador tem escolhas em cada turno para o próximo movimento e, na ausência de erros estúpidos, o número de turnos é sempre entre e . Tão grosseiramente, a árvore do jogo possui estados. Se você explorou a árvore do jogo com força bruta, pode gastar um tempo exponencial para encontrar uma jogada vencedora ou convencer-se de que não pode vencer.Θ ( N ) N 6 N N Θ ( N )3NΘ(N)N6NNΘ(N)

Mas, de fato, Uri Zwick provou em 2005 que você pode jogar Jenga perfeitamente, acompanhando apenas três números inteiros, usando um conjunto simples de regras que você pode encaixar facilmente em um cartão de visita. Os três números que você precisa são

  • m= o número de níveis (sem contar o nível superior) com três tijolos.
  • n= o número de níveis (sem contar o nível superior) com dois tijolos lado a lado.
  • t= o número de tijolos no nível superior (0, 1, 2 ou 3).

De fato, na maioria das vezes, você só precisa se lembrar de e vez de e . Aqui está a estratégia completa para ganhar:nmod3mmod3nm

insira a descrição da imagem aqui

Aqui II significa que você deve mover o tijolo do meio de qualquer camada 3 no topo, II- significa que você deve mover um tijolo de lado de uma camada 3 para o topo, -I- significa que você deve mover o tijolo do lado de uma camada 2 para o topo, e o bob-omb significa que você deve pensar na morte e ficar triste e tal . Se houver mais de um movimento sugerido em uma caixa, você poderá escolher qualquer um deles. É trivial executar essa estratégia no tempo se você já conhece o tempo triplo , ou no tempo se não conhece .O(1)(m,n,t)O(N)

Moral: Jenga só é divertido se todos forem desajeitados e / ou bêbados.

Jeffε
fonte
Esse é um excelente exemplo de ensino, mas eu daria o +1 apenas para a referência de Peregrino.
Luke Mathieson
10

Um caixa deve devolver centavos de alteração a um cliente. Dadas as moedas que ela tem disponíveis, ela pode fazê-lo e como?x

  • Força bruta: considere todas as coleções possíveis de moedas e veja se uma delas soma .x
  • Força não bruta: faça como todo caixa, por programação dinâmica.

Existem duas variantes do problema:

  1. Fácil : o caixa tem suprimento ilimitado de todas as denominações.
  2. Mais difícil: o caixa tem um suprimento limitado de moedas.

A variante fácil pode ser resolvida com um algoritmo ganancioso. O mais difícil requer programação dinâmica.

Na verdade, a maneira de apresentar isso é propor a solução de força bruta, fazer com que as pessoas entendam que é muito ineficiente e, em seguida, perguntar-lhes o que os caixas fazem, primeiro pela variante fácil e depois pela difícil. Você deve ter alguns exemplos disponíveis que vão de fácil a desagradável.

Andrej Bauer
fonte
1

Acho que encontrei um exemplo útil!

Talvez eu estivesse um pouco vago, mas estava procurando um problema que atendesse às seguintes especificações:

  • O problema em si deve ser fácil de explicar para alguém que estuda ciências sociais.
  • Deve ter um algoritmo óbvio, mas ineficaz.
  • Deveria ter um algoritmo melhor, fácil de explicar para quem estuda ciências sociais.

Para o Ciclo Euleriano, é fácil explicar que é uma condição necessária para que cada nó tenha um grau uniforme, mas não é tão fácil explicar por que é uma condição suficiente.

Este é o problema que, até agora, acho que melhor atende à especificação acima:

FORM_TARGET_SET_WITH_UNIONS

Coleção de conjuntosC={S1,S2,...,Sn}

Conjunto de metasT

Pergunta: É possível formar o conjunto de destino tomando a união de alguns dos conjuntos em ?TC

Algoritmo óbvio, mas ineficaz:

  • Forme todas as uniões possíveis2n
  • Veja se um deles corresponde aT

Algoritmo melhor

  • Marque os conjuntos em que estão contidos emCT
  • Forme a união desses conjuntosS
  • Seresponda , caso contrário responda|S|=|T|YESNO

Há também o problema da irmã

FORM_TARGET_SET_WITH_INTERSECTIONS

para o qual o melhor algoritmo é

  • Marque os conjuntos em que contêmCT
  • Forme a interseção desses conjuntosS
  • Seresponda , caso contrário responda|S|=|T|YESNO

Como você pode ver, eu estava procurando por algo realmente simples (quase tão simples quanto SUBSET_PRODUCT_IS_ZERO).

O problema também pode ser contrastado com SUBSET SUM e SUBSET PRODUCT, que são NP completos, mas similares em sua formulação. Em todos esses problemas, é apresentado um conjunto de objetos e perguntado se uma operação em uma seleção desses objetos pode produzir o resultado desejado.

sixpanbass
fonte
1
Outros problemas são primalidade , Horn-SAT e correspondência máxima .