Mark Dominus coletou alguns exemplos de reduções no tempo polinomial de vários problemas difíceis de NP para correspondência de "expressão regular" . Visualizar verificações em tempo polinomial não é um salto enorme.
Como você ilustra a classe NP-complete para estudantes de graduação ou para amigos de outras áreas que queriam entender a recente confusão sobre o trabalho de Deolalikar?
np-hardness
big-list
Greg Bacon
fonte
fonte
Alguns problemas "todos os dias" que são difíceis de NP, adequadamente formulados:
Atribuir turmas universitárias a intervalos de tempo para minimizar conflitos de agendamento.
Designando convidados do casamento para assentos, para que os amigos se sentem na mesma mesa, mas os inimigos não.
Planejando uma viagem para visitar todos os pontos turísticos de uma lista, para minimizar a direção.
fonte
O problema do vendedor ambulante é aparentemente acessível ... pelo menos onde estou, esse parece ser o problema mais popular de CS entre pessoas que não são de CS. Também achei a ilustração a seguir do Vertex Cover bastante atraente, como foi introduzida por meu instrutor de algoritmos:
Você tem uma rede de estradas e deseja garantir que, se um carro estiver sem combustível, haja um posto de gasolina em pelo menos um extremo da estrada.
Como planejador da cidade, você deseja minimizar os custos criando o menor número possível de postos de gasolina. Esse é essencialmente o problema da cobertura de vértices, e obtive algum sucesso ao apontar que, embora você não espere encontrar a cobertura ideal de vértices no tempo polinomial, é possível encontrar algo que está apenas a um fator de dois no tempo polinomial, simplesmente escolhendo os dois pontos de extremidade de uma correspondência máxima (bem, esse último detalhe pode ser omitido dependendo do interesse de seu público - especialmente porque o algoritmo MM não é exatamente uma linha dupla).
Quanto a um exemplo de um "salto na complexidade" com uma pequena mudança na natureza do problema, acho que a diferença entre verificar a 2 cores e a 3 cores é um bom exemplo. Com toda a publicidade em torno do teorema das quatro cores, pode-se também apontar que verificar se um mapa pode ser adequadamente colorido com apenas três cores em vez de quatro é difícil, mesmo sabendo que sempre pode ser colorido com quatro cores. Um bom número de pessoas acha isso bastante surpreendente.
Outra situação bastante natural é o problema de recuperação de impasse nos sistemas operacionais. Isso é modelado pelo problema NP-completo do conjunto de vértices de feedback - o menor número de vértices cuja remoção torna o gráfico acíclico - e também acho esse um exemplo notável (e é explicado mais detalhadamente nesse artigo da wikipedia).
fonte
Eu acho que o estacionamento paralelo é difícil para NP.
De fato, o problema mais geral de encontrar o caminho mais curto com curvatura limitada que leva um objeto poligonal de sua posição inicial para sua posição final em um ambiente poligonal é difícil para NP. A prova pode ser encontrada aqui - http://portal.acm.org/citation.cfm?id=298976
fonte
A mochila é muito fácil de entender, especialmente para quem já teve que lidar com uma mala pequena. Um bom exemplo se eles conhecem programação dinâmica.
Outra divertida (praticamente idêntica) é a soma de subconjuntos, porque também tem uma boa interpretação física: imagine os números sendo as distâncias de massas pontuais iguais em uma régua ideal (sem massa), com o ponto de apoio na origem. A soma do subconjunto diz: existe um subconjunto não vazio de forma que a régua permaneça equilibrada? (ou seja, de modo que o centro de gravidade seja o ponto de apoio para a régua?)
Nos dois casos, parece intuitivo que estratégias ingênuas possam forçar o recurso à verificação de todos os subconjuntos.
Se eles tiverem mais experiência, é bom criar problemas eliminando restrições. Por exemplo, começando com um problema de fluxo máximo, transformando-o em um programa linear e tornando-o um programa inteiro. É claro que o MAX-CUT é excelente, pois para pessoas com mais experiência também é possível criar o UGC; eu toquei um pouco disso em uma resposta MO https://mathoverflow.net/questions/33036/is-quadratic-programming (ainda assim, np-difícil-se-você-tem-limites-e-um-ponto-factível / 33048 # 33048 ). Também existem coisas legais, como problemas aparentemente semelhantes que têm uma complexidade muito diferente (o caminho de Euler (borda) é linear tempo, o caminho Hamiltoniano (vértice) é NP-completo).
fonte
A construção de palavras cruzadas é NP-Complete: Dado um conjunto de respostas, tente encaixá-las em uma grade.
fonte
Criei o site Tagxedo, http://www.tagxedo.com , um gerador de nuvem de palavras que encaixa as palavras (dimensionadas por suas frequências) em forma. Os resultados são muito bonitos, mas o problema é facilmente comprovado como NP-difícil (problema de empacotamento).
Curiosamente, muitos problemas difíceis de NP têm aproximações "fáceis". Tagxedo parece estar fazendo um trabalho quase perfeito em muitos casos. Isso leva a uma discussão interessante sobre a implicação prática de P vs NP e o tópico de aproximação.
fonte
Um dos meus amigos passou um ano sabático assistindo a um jogo de beisebol em todos os estádios da liga principal da América do Norte. Sem voar. (Ele não bastante sucesso, três estádios estavam em construção naquele ano.)
fonte
Devido ao sucesso de empresas como Uber e Lyft, muitas pessoas têm uma experiência direta muito acessível com problemas de NP-completos.
Esse problema (quando reformulado adequadamente) é o NPC e imagino que as pessoas já se perguntaram em algum momento como o Uber decide emparelhar motoristas e passageiros.
fonte
Eu costumo usar SAT como um exemplo. Eu digo algo como "todos os tipos de problemas que surgem o tempo todo podem ser reescritos, procurando uma verdadeira atribuição para uma grande fórmula lógica. A questão P vs NP é se existe uma maneira fundamentalmente mais fácil de resolver essa fórmula lógica do que apenas tentando todas as possibilidades. Até agora ninguém foi capaz de encontrar um caminho ou provar que não há uma saída fácil ".
fonte
Um problema Np-completo como o Sudoku (no nxn sqaure) é como uma ferramenta Universal que nos permite resolver com eficiência todos os problemas que possuem soluções eficientemente verificáveis. O único requisito é ter um método eficiente para resolver o Sudoku.
fonte
Espero que isto ajude!
fonte
Um exemplo caprichosamente acessível é uma breve apresentação de Mark Dominus (consulte a postagem do blog relacionada ) chamada “Meu Problema Completo de NP Favorito”, onde a imagem abaixo é o ponto final de uma visão geral da cobertura exata de 3 conjuntos .
Os títulos da série de vídeos incluem
A intenção clara era que cada vídeo contivesse três episódios, todos sobre um tema comum, extraído de um conjunto de tópicos de interesse para crianças pequenas.
O estranho pato da série foi um vídeo sobre "flores, bananas e ... cabelos".
fonte
Especialmente quando analisamos o problema da mochila mais tarde, esse problema NP-completo pode ser uma boa opção:
Adivinhação de números, onde você só pode adivinhar números únicos até acertar.
fonte