Estou pensando no seguinte problema há um tempo e não encontrei uma solução polinomial para ele. Apenas fonte bruta. Eu também tenho tentado reduzir um problema NP-Complete sem sucesso. Aqui está o problema : Você tem um conjunto classificado de pares inteiros positivos. { ( A1, B1) , ( A2, B2)...
Achei este artigo muito interessante. Para resumir: ele discute por que, na prática, você raramente encontra a pior das hipóteses de um problema completo de NP. A idéia no artigo é que as instâncias geralmente são muito sub ou muito restritas, e ambas são relativamente fáceis de resolver. Em...
O seguinte problema é NP-difícil? Dada a configuração do quadro para rascunhos internacionais , encontre uma única jogada legal.n × nn×nn\times n O problema correspondente para damas americanas (também conhecidas como rascunhos em inglês) é trivialmente solucionável em tempo polinomial....
Considere o problema mínimo de cobertura do conjunto com as seguintes restrições: cada conjunto contém no máximo kkk elementos e cada elemento do universo ocorre no máximo fff conjuntos. Exemplo: o caso k=4k=4k = 4 e f=2f=2f = 2 é equivalente ao problema de cobertura mínima de vértice em gráficos...
A complexidade do seguinte problema foi estudada? Entrada : um gráfico cúbico (ou regular) , um limite superior naturalG = ( V , E ) t333G = ( V, E)G=(V,E)G=(V,E)ttt Pergunta : existe uma partição de em partes do tamanho tal forma que a soma das ordens dos subgráficos correspondentes...
Existem referências sobre
Considere o seguinte problema: dada uma fórmula CNF e uma atribuição que satisfaça essa fórmula, existe outra atribuição satisfatória para essa fórmula? Qual é a complexidade desse problema? (Certamente está em NP, mas também é difícil em NP?) E se você não receber a tarefa e apenas quiser...
Para qualquer , digo que uma sequência de números inteiros em é completa se, para cada permutação de , escrita como uma sequência de números inteiros distintos , a sequência é uma subsequência de , ou seja, existede modo que para todos os .s { 1 , … , n } n p { 1 , … , n } p 1 , … , p n p s 1 ≤ i 1...
Sabe-se que é NP-completo testar se existe um ciclo hamiltoniano em um gráfico tridimensional, mesmo que seja plano (Garey, Johnson e Tarjan, SIAM J. Comput. 1976) ou bipartido (Akiyama, Nishizeki, e Saito, J. Inform. Proc. 1980) ou para testar se existe um ciclo hamiltoniano em um gráfico de 4...
Há uma literatura rica e pelo menos um livro muito bom que define a dureza conhecida dos resultados da aproximação para problemas difíceis de NP no contexto de erro multiplicativo (por exemplo, 2 aproximações para cobertura de vértices é ideal, considerando UGC). Isso também inclui classes de...
O problema Nem todos iguais -SAT (NAE k -SAT), dado um conjunto C de cláusulas sobre um conjunto X de variáveis booleanas, de modo que cada cláusula contém no máximo k literais, pergunta se existe uma atribuição de verdade das variáveis, de forma que cada cláusula contém pelo menos um literal...
Estou interessado no problema de empacotar cópias idênticas de retângulos (bidimensionais) em um polígono convexo (bidimensional) sem sobreposições. No meu problema, você não tem permissão para girar os retângulos e pode assumir que eles estão orientados paralelamente aos eixos. Você recebe as...
Para uma constante , pode-se determinar em tempo linear, dado um gráfico de entrada , se sua largura de árvore é . No entanto, quando e são dados como entrada, o problema é NP-difícil. ( Fonte ). G ≤ k k Gk ∈ Nk∈Nk \in \mathbb{N}GGG≤ k≤k\leq kkkkGGG No entanto, quando o gráfico de entrada é plano...
Esta pergunta está relacionada a uma resposta que eu postei em resposta a outra pergunta. O problema de 3 partições é o seguinte: Instância : números inteiros positivos a 1 ,…, a n , em que n = 3m e a soma dos n números inteiros é igual a mB, de modo que cada a i satisfaça B / 4 <a i <B /...
Há claramente uma redução de CLIQUE para k-Color porque ambos são NP-Complete. Na verdade, eu posso construir um compondo uma redução de CLIQUE para 3-SAT com uma redução de 3-SAT para k-Color. O que eu quero saber é se existe uma redução direta razoável entre esses problemas. Digamos, uma redução...
Sabe-se que o ciclo hamiltoniano (presunto abreviado) é NP-completo e que o ciclo planar de presunto é NP-completo. A prova para o Ciclo de Presunto Planar não é do Ciclo de Presunto. Existe um gadget legal que, dado um gráfico G, substitua todos os cruzamentos por algum gadget planar, para que...
Eu estava lendo " O P Versus NP é formalmente independente? ", Mas fiquei intrigado. É amplamente aceito na teoria da complexidade que . Minha pergunta é sobre o que se não for possível (digamos no ). (Vamos supor que descobrimos apenas que é independente do mas não há mais informações sobre como...
todo mundo sabe que existem muitos problemas de decisão que são difíceis de NP em gráficos gerais, mas estou interessado em problemas que são difíceis de NP quando o gráfico subjacente é um caminho. Então, você pode me ajudar a coletar esses problemas? Eu já encontrei uma pergunta relacionada...
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...
A redação exata do título deve-se a Anand Kulkarni (que propôs a criação deste site). Esta pergunta foi feita como exemplo, mas estou insanamente curiosa. Eu sei muito pouco sobre geometria algébrica e, de fato, também só tenho uma compreensão superficial dos obstáculos em jogo na questão P / poli...