Em computabilidade e complexidade, localizando mapeamentos entre problemas que permitem solucionar um problema usando uma solução de outro. Para redução na teoria da linguagem de programação (por exemplo, redução beta), consulte [lambda-calculus] ou [term-reescrevendo].
Na teoria da computabilidade e da complexidade (e talvez em outros campos), as reduções são onipresentes. Existem muitos tipos, mas o princípio permanece o mesmo: mostre que um problema é pelo menos tão difícil quanto outro problema mapeando instâncias de para instâncias a solução em ....
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...
Estou fazendo um curso de complexidade e estou tendo problemas para apresentar reduções entre os problemas dos NPCs. Como posso encontrar reduções entre problemas? Existe um truque geral que eu possa usar? Como devo abordar um problema que me pede para provar que é um
Estou interessado na questão de qual a melhor maneira de ensinar a NP-completude aos cursos de ciência da computação. Em particular, devemos ensiná-lo usando reduções de Karp ou reduções de Turing? Sinto que os conceitos de completude e redução de NP são algo que todo especialista em ciência da...
Um número surpreendente de problemas tem reduções bastante naturais na programação linear (LP). Veja o Capítulo 7 de [1] para exemplos como fluxos de rede, correspondência bipartida, jogos de soma zero, caminhos mais curtos, uma forma de regressão linear e até avaliação de circuitos! Como a...
Digamos que exista um programa que, se você der um Sudoku parcialmente preenchido de qualquer tamanho, ele fornecerá o Sudoku completo correspondente. Você pode tratar esse programa como uma caixa preta e usá-lo para resolver o TSP? Quero dizer, existe uma maneira de representar o problema do TSP...
O que eu quero fazer é transformar um problema de matemática que possuo em um problema de satisfação booleana (SAT) e resolvê-lo usando um SAT Solver. Gostaria de saber se alguém conhece um manual, guia ou qualquer coisa que me ajude a converter meu problema em uma instância SAT. Além disso, quero...
O problema da soma de subconjuntos é um problema NP-completo clássico: Dada uma lista de números e um destino , existe um subconjunto de números de que soma ?k L keuLLkkkeuLLkkk Um aluno me perguntou se essa variante do problema chamada de "produto de subconjunto" está NP-completa: Dada uma...
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...
Deixe-me começar por observar que este é um problema de lição de casa; forneça apenas conselhos e observações relacionadas; NENHUMA RESPOSTA DIRETA por favor . Com isso dito, aqui está o problema que estou olhando: Vamos MEIA CLIQUE = { | é um gráfico não direcionado com um subgráfico completo...
Talvez isso seja bastante simples, mas tenho alguns problemas para obter essa redução. Eu quero reduzir a soma de subconjuntos à partição, mas neste momento não vejo a relação! É possível reduzir esse problema usando uma redução de Levin? Se você não entende, escreva para...
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...
No artigo Complexidade do Problema de Frobenius, de Ramírez-Alfonsín, um problema foi comprovado como NP-completo usando reduções de Turing. Isso é possível? Como exatamente? Eu pensei que isso só era possível por um tempo polinomial de muitas reduções. Há alguma referência sobre isso? Existem...
Graças ao teorema min-cut de fluxo máximo, sabemos que podemos usar qualquer algoritmo para calcular um fluxo máximo em um gráfico de rede para calcular um -min-cut. Portanto, a complexidade de calcular um corte mínimo ( s , t ) não é mais do que a complexidade de calcular um fluxo máximo ( s , t )...
Em todo lugar, os livros de texto assumem que o Problema de correspondência pós encadernada é NP completo (não são permitidos mais do que índices permitidos com repetições). No entanto, em nenhum lugar é mostrada uma redução de tempo polinomial simples (como em algo que um aluno de graduação pode...
Estou lutando para entender a relação entre NP-Intermediário e NP-Completo. Eu sei que se P! = NP baseado no Teorema de Ladner, existe uma classe de idiomas em NP, mas não em P ou em NP-Complete. Todo problema no NP pode ser reduzido a um problema NP-Complete, no entanto, não vi exemplos para...
Aparentemente, se , todos os idiomas em exceto e seriam completos.P=NPP=NP{\sf P}={\sf NP}PP{\sf P}∅∅\emptysetΣ∗Σ∗\Sigma^*NPNP{\sf NP} Por que essas duas línguas em particular? Não podemos reduzir nenhum outro idioma em para eles, exibindo-os ao aceitar ou não?PP{\sf...
Seja A redutível a B, isto é, A≤BA≤BA \leq B . Assim, a máquina de Turing aceitar AAA tem acesso a um Oracle para BBB . Permita que a máquina de Turing que aceita AAA seja MAMAM_{A} e o oráculo para BBB seja . Os tipos de reduções:OBOBO_{B} Redução de Turing: pode fazer várias consultas para . O...
Nós temos um DAG. Temos uma função nos nós (falando livremente, numeramos os nós). Gostaríamos de criar um novo gráfico direcionado com estas regras:F:V→NF:V→NF\colon V\to \mathbb N Somente nós com o mesmo número podem ser contratados no mesmo novo nó. . (No entanto,...
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...