problemas de decisão que são pelo menos tão difíceis quanto problemas NP-completos
A maior parte da criptografia de hoje, como o RSA, depende da fatoração de número inteiro, que não se acredita ser um problema difícil de NP, mas pertence ao BQP, que o torna vulnerável a computadores quânticos. Eu me pergunto, por que não houve um algoritmo de criptografia baseado em um problema...
Existem nnn caixas e mmm tipo de bolas. O iii th bin tem rótulos ai,jai,ja_{i,j} para 1≤j≤m1≤j≤m1\leq j\leq m , que é o número esperado de bolas do tipo jjj . Você começa com bjbjb_j bolas do tipo jjj . Cada esfera de tipo jjj tem peso wjwjw_j , e deseja colocar as bolas dentro dos recipientes de...
Gostaria de saber se existe um bom exemplo para um problema NP-Hard fácil de entender que não é NP-Complete e não é indecidível? Por exemplo, o problema de parada é NP-Hard, não NP-Complete, mas é indecidível. Acredito que isso significa que é um problema que uma solução pode ser verificada, mas...
A Wikipedia e outras fontes que eu encontrei listam o voidtipo de C como um tipo de unidade, em vez de um tipo vazio. Acho isso confuso, pois me parece que voidmelhor se ajusta à definição de um tipo vazio / inferior. Nenhum valor habita void, até onde eu sei. Uma função com um tipo de retorno de...
Dado intervalos de tempo que k pessoas querem comprar. A pessoa i tem um valor h ( i , j ) ≥ 0 para cada intervalo de tempo j . Cada pessoa pode comprar apenas um bloco consecutivo de horários, que podem estar vazios.nnnkkkEuiih ( i , j ) ≥ 0h(i,j)≥0h(i,j)\geq 0jjj Existe um algoritmo de tempo...
Vamos supor que . N P I é a classe de problemas em N P que não são nem P nem em N P -Hard. Você pode encontrar uma lista de problemas conjecturados como N P I aqui .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Teorema de Ladner...
Aqui está o problema. Dado , em que cada . Existe um subconjunto com tamanho máximo de tal que para todos os ? Estou tentando reduzir esse problema para o SAT. Minha idéia de uma solução seria ter uma variável para cada um de 1 a . Para cada , crie uma cláusula se . Então e todas essas cláusulas...
A Wikipedia declara o problema da soma do subconjunto como encontrar um subconjunto de um determinado conjunto múltiplo de números inteiros, cuja soma é zero. Além disso, afirma que é equivalente a encontrar um subconjunto com soma para qualquer dado .ssssss Então, acredito que, como são...
Como posso provar que a conversão de CNF para DNF é NP-Hard? Não estou pedindo uma resposta, apenas algumas sugestões sobre como proceder para provar
É necessário que um problema difícil de NP seja computável? Acho que não, mas não tenho
Há uma redução no livro de Sipser "Introdução à teoria da computação" na página 286, do 3SAT para o problema do caminho hamiltoniano. Existe uma redução mais simples? Por mais simples, quero dizer uma redução que seria mais fácil de entender (para os alunos). Existe uma redução que usa...
Um Hidoku é uma grade com alguns números inteiros pré-preenchidos de 1 a . O objetivo é encontrar um caminho de números inteiros sucessivos (de 1 a ) na grade. Mais concreto, cada célula da grade deve conter um número inteiro diferente de 1 a e cada célula com valor deve ter uma célula vizinha com...
Um quebra-cabeça "Flow Free" consiste em um número inteiro positivo e um conjunto de pares (não ordenados) de vértices distintos no gráfico da grade modo que cada vértice esteja no máximo em um par. Uma solução para esse quebra-cabeça é um conjunto de caminhos não direcionados no gráfico, de modo...
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...
Qual é a complexidade de e \ text {MAX-2-XOR-SAT} ? Eles estão em P? Eles são NP-difíceis?MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT}MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} Para formalizar isso com mais precisão, vamos Φ(x)=∧niCi,Φ(x)=∧inCi,\Phi\left(\mathbf...
Eu estava brincando no outro dia neste site: http://regexcrossword.com/ e isso me fez pensar em qual seria a melhor maneira de resolvê-lo. Você pode resolver o seguinte problema em tempo polinomial ou é NP-difícil? Dada uma grade NxM com N expressões regulares para as colunas e M para as...
A integridade do coNP implica dureza do NP? Em particular, tenho um problema que demonstrei ser coNP-completo. Posso afirmar que é NP-difícil? Percebo que posso reivindicar dureza de coNP, mas não tenho certeza se essa terminologia é padrão. Estou satisfeito com a afirmação de que, se um problema...
A Rodada de Teste do Google Hash Code 2015 ( declaração do problema ) perguntou sobre o seguinte problema: entrada: uma grade com alguns quadrados marcados, um limiar T ∈ N , uma área máxima A ∈ NMMMT∈NT∈NT \in \mathbb{N}A∈NA∈NA \in \mathbb{N} produção: a maior área possível total de um conjunto...
Suponha que eu sou dado um conjunto finito de pontos no plano, e pediu para desenhar um duas vezes diferenciável curva C ( P ) através do p i 's, de tal modo que o seu perímetro seja tão pequena quanto possível. Supondo que p i = ( x i , y i ) e x i < x i + 1 , posso formalizar esse problema...
Eu tenho uma tarefa de casa em que tenho criticado há algum tempo e gostaria de receber qualquer dica. Trata-se de escolher um problema conhecido, cuja integridade do NP é comprovada, e construir uma redução desse problema para o seguinte problema, que chamarei DGD (diagnóstico de gráfico...