MEIA CLIQUE - NP Complete Problem

20

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 com pelo menos nós, em que n é o número de nós em }. Mostre que HALF-CLIQUE está NP-completo.GGn/2G

Além disso, eu sei o seguinte:

  • Em termos desse problema, um clique é definido como um subgráfico não direcionado do gráfico de entrada, em que cada dois nós são conectados por uma aresta. Uma -clique é uma clique que contém nós.kk
  • De acordo com nosso livro, Michael Sipser " Introdução à teoria da computação ", página 268, que o problema CLIQUE = { | é um gráfico não direcionado com uma -clique} está em NPG,kGk
  • Além disso, de acordo com a mesma fonte (na página 283), observa que o CLIQUE está no NP-Complpete (portanto, obviamente também no NP).

Acho que tenho o núcleo de uma resposta aqui, no entanto, eu poderia usar alguma indicação do que há de errado com ela ou quaisquer pontos relacionados que possam ser relevantes para uma resposta . Esta é a ideia geral que tenho até agora,

Ok, gostaria de observar primeiro que um certificado seria simplesmente um MEIO QLIQUE de . Agora, parece que o que eu precisaria fazer é criar um verificador que reduza o tempo polinomial de CLIQUE (que sabemos que é NP-Complete) para HALF-CLIQUE. Minha idéia seria que isso fosse feito criando uma máquina de Turing que executa o verificador da máquina de turing no livro para CLIQUE com a restrição adicional para HALF-CLIQUE.sizen/2

Isso me parece correto, mas ainda não confio em mim mesmo neste assunto. Mais uma vez, gostaria de lembrar a todos que este é um PROBLEMA EM CASA , por isso tente evitar responder à pergunta. Qualquer orientação que fique aquém disso seria muito bem-vinda!

BrotherJack
fonte

Respostas:

15

A julgar pela sua descrição e comentários, você pode ser ajudado da melhor maneira por uma descrição exata de como as reduções podem ser usadas para provar a integridade do NP:

Um problema é NP-completo se estiver no NP e for NP-difícil. Isso significa que qualquer prova de integridade do NP tem duas partes: uma prova de que o problema está no NP e uma prova de que é NP-difícil.

Para a primeira parte, você deve mostrar que as instâncias YES podem ser verificadas em tempo polinomial usando algum certificado adequado. Como alternativa, você pode mostrar que o problema pode ser resolvido em tempo polinomial por uma máquina de Turing não determinística, mas isso geralmente não é feito, pois os erros são facilmente cometidos.

n/2

Para a segunda parte, você precisa mostrar que o problema é difícil para o NP. Isso é mostrado em quase todos os casos, comprovando que seu problema é pelo menos tão difícil quanto outro problema difícil de NP. Se o HALF-CLIQUE for tão duro quanto o CLIQUE, também deverá ser NP-hard.

Você faz isso através da prova de uma redução DE CLIQUE, AO MEIO-CLIQUE. Você 'reduz' o problema, tornando-o 'mais fácil'. Você diz "A solução do CLIQUE é difícil, mas eu provei que você só precisa resolver o HALF-CLIQUE para resolver o CLIQUE". (muitas pessoas, até mesmo especialistas, ocasionalmente dizem isso da maneira errada :))

Existem diferentes tipos de reduções: a redução mais comumente usada é aquela em que você mapeia instâncias, neste caso, CLIQUE, para instâncias de HALF-CLIQUE cujo tamanho é no máximo polinomialmente maior, em tempo polinomial. Isso significa que, se podemos resolver o HALF-CLIQUE, também podemos resolver o CLIQUE encadeando o algoritmo e a redução.

Em outras palavras, devemos mostrar que podemos resolver o CLIQUE se pudermos resolver o HALF-CLIQUE. Fazemos isso mostrando que, para cada instância do CLIQUE, podemos projetar uma instância do HALF-CLIQUE de modo que a instância do CLIQUE seja uma instância 'yes' se a instância do HALF-CLIQUE for uma instância 'yes'.

G=(V,E)H=(V,E)GkHn/2

Alex ten Brink
fonte
Excelente configuração, acho que você fez um bom trabalho ao fornecer informações suficientes para orientar sem fornecer uma resposta e fazê-lo de maneira eloqüente. Obrigado.
BrotherJack
1
Algo assim deve ser colocado na tag wiki do np-complete para referência futura. Você se importaria?
Raphael
8

GkHHGk

O spoiler abaixo contém uma dica sobre como realizar essa redução:

HG

Louis
fonte
Não estou entendendo o que você está dizendo. O que tentei fazer foi reduzir o HALF-CLIQUE para o CLIQUE, modificando o varificador usado no livro para provar que o CLIQUE era NP, execute-o no gráfico de entrada G e se encontrasse um CLIQUE verificando se o referido CLIQUE continha pelo menos n / 2 nós, em que n é o número de nós em G. Esse verificador de HALF-CLIQUE não mostraria que o verificador de CLIQUE é uma forma reduzida dele (como em um subproblema de resolução de HALF-CLIQUE )?
BrotherJack
Ou você está dizendo que eu o tenho ao contrário e preciso provar que o CLIQUE precisa ser reduzido para MEIO-CLIQUE? Também não estou entendendo completamente o seu spoiler. Existe alguma maneira de explicar isso sem dar a resposta?
BrotherJack
3
Sim, para mostrar um problema é NP-completo, você precisa (a) mostrar que está em NP e (b) reduzir algum problema NP-hard conhecido para ele. Para lembrar a direção certa para a redução, o objetivo é usar o novo problema como uma "caixa preta" para resolver com eficiência um problema conhecido de NP-C.
Louis
OK, acho que entendo agora. Obrigado pela ajuda!
BrotherJack
+1 Acho que entendi. Sua dica foi muito instrutiva depois que eu entendi o que estava fazendo de errado. Obrigado novamente!
BrotherJack
0

Você pode reduzir a partir do problema de cobertura de vértice. Se o gráfico de complemento do gráfico fornecido tiver uma cobertura de vértice menor que n / 2 nós, este gráfico terá um clique de mais de n / 2 nós, ou seja, será um clique de meia. Apenas diga que é difícil resolver o problema da Vertex Cover, assim é.

Arnav
fonte
1
Como você pode reduzir de qualquer problema NP-completo, isso não é muito útil. Detalhes sobre a redução são esperados.
Raphael
n/2