Está provado que a computação quântica não é melhor na solução de problemas completos de NP do que a computação clássica ou apenas se
Gostaria de saber qual é o algoritmo mais conhecido, em termos de notação Big- , para resolver a Programação Linear Inteira?OOO Eu sei que o problema é completo, então não estou esperando nada polinomial. E eu sei que existem muitas heurísticas e outras que são usadas em aplicações práticas como o...
Se fato é igual a N P , como isso aprimora nossos algoritmos para fatorar números inteiros mais rapidamente. Em outras palavras, que tipo de insight esse fato nos daria para entender melhor a fatoração inteira?PP{\sf P}N PNP{\sf
Tenho certeza de que alguém já pensou nisso antes ou imediatamente o descartou, mas por que a teoria da dicotomia de Schaefer, juntamente com o teorema de Mahaney sobre conjuntos esparsos, não implica P = NP? Aqui está o meu raciocínio: Crie um idioma que seja igual a SAT cruzado por um conjunto...
Meu palestrante fez a declaração Qualquer problema finito não pode ser NP-Complete Ele estava falando sobre o Sudoku na época dizendo algo do tipo: para um Sudoku 8x8, existe um conjunto finito de soluções, mas não me lembro exatamente o que ele disse. Anotei a nota que citei, mas que ainda...
O conhecido problema SAT é definido aqui para fins de referência. O problema DOUBLE-SAT é definido como DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has...
O problema 3-partição pergunta se um conjunto de inteiros pode ser dividida em n conjuntos de três números inteiros tais que cada conjunto somas até algum dado número inteiro B . O problema da partição balanceada pergunta se 2 n inteiros podem ser particionados em dois conjuntos iguais de...
Suponha que exista uma sessão de tutorial em uma universidade. Temos um conjunto de perguntas e um conjunto de alunos . Cada aluno tem uma dúvida em um determinado subconjunto de perguntas, ou seja, para cada aluno , seja o conjunto de perguntas que um aluno duvida. Assume-se que e...
Em termos de pior tempo de execução assintótico, qual problema de NP-completo possui o algoritmo mais rápido (exato) conhecido e qual é o algoritmo? Existe algo conhecido que é mais rápido que O(n2∗2n)O(n2∗2n)O(n^2*2^n)
Estou tentando resolver esse problema e estou realmente lutando. Uma fórmula booleana monótona é uma fórmula na lógica proposicional em que todos os literais são positivos. Por exemplo, (x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor...
Esta é provavelmente uma pergunta estúpida, mas eu simplesmente não entendo. Em outra questão, eles apresentaram o teorema da dicotomia de Schaefer . Para mim, parece que prova que todo problema de CSP está em P ou em NP-complete, mas não no meio. Como todo problema de NP pode ser transformado no...
Eu li sobre o NPC e sua relação com o PSPACE e gostaria de saber se os problemas do NPC podem ser resolvidos deterministicamente usando um algoritmo com o pior requisito de espaço polinomial, mas potencialmente levando tempo exponencial (2 ^ P (n) onde P é polinomial). Além disso, ele pode ser...
A dificuldade de um problema fortemente NP-difícil ou NP-completo (como por exemplo, definido aqui ) muda quando sua entrada é unária em vez de codificada em binária? Que diferença faz se a entrada de um problema fortemente NP-difícil é unária? Quero dizer, se eu pegar, por exemplo, o problema...
Então, eu sei que testar se uma linguagem regular RRR é um subconjunto de linguagem regular SSS é decidível, já que pode converter-los tanto para DFAs, compute R∩S¯R∩S¯R \cap \bar{S} , e em seguida, teste se esta linguagem é vazia. No entanto, como isso requer conversão em DFAs, é possível que os...
Supondo que temos um problema e mostramos que o limite inferior para resolver é .ppppppΩ(2n)Ω(2n)\mathcal{\Omega}(2^n) O limite inferior implica o problema no
Eu sei que o conjunto independente máximo em gráficos sem triângulo cúbico é NP-completo. Ainda é NP-completo no caso de exigirmos que o conjunto independente seja do tamanho exato ?|V|/2|V|/2|V|/2 Basicamente, a instância YES de um problema de conjunto independente em gráficos sem triângulo...
O seguinte problema é NP-completo? (Presumo que sim). Entrada: um gráfico não direcionado em que o conjunto de arestas pode ser decomposto em dois ciclos simples separados por arestas (estes não fazem parte da entrada).k∈N,G=(V,E)k∈N,G=(V,E)k \in \mathbb{N},G=(V,E) Pergunta: Existe um ciclo...
No trabalho, fui encarregado de deduzir algumas informações de tipo sobre uma linguagem dinâmica. Reescrevo seqüências de instruções em letexpressões aninhadas , da seguinte maneira: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z =>...
Gostaria de saber se existe um algoritmo polinomial para "2-SAT com relações XOR". O 2-SAT e o XOR-SAT estão em P, mas é sua combinação? Exemplo de entrada: Parte 2-SAT: (a or !b) and (b or c) and (b or d) Parte XOR: (a xor b xor c xor 1) and (b xor c xor d) Em outras palavras, a entrada é a...
Existem algoritmos conhecidos que emitem corretamente "yes" para um problema NP-completo sem gerar implicitamente um certificado? Entendo que é fácil transformar um oráculo de satisfação em um localizador de tarefas satisfatórias: apenas itere sobre as variáveis, sempre pedindo ao oráculo de...