Algoritmo Polytime para SUBSET-SUM assumindo P = NP

Na página da Wikipedia no problema P vs. NP, existe um algoritmo que "resolve" SUBSET-SUM no caso de P = NP em tempo polinomial. (A idéia é encontrar uma TM que dê um certificado). Mas dá "sim" no tempo polinomial e dura para sempre se a resposta for "não". Obviamente, pode ser corrigido para dar "não" em tempo exponencial (apenas para executar o algoritmo exponencial se o primeiro estiver em execução por muito tempo).

Mas podemos descrever explicitamente um algoritmo "honesto", que resolve (e quero dizer, resolve realmente) SUBSET-SUM (ou qualquer outro problema de NP-completo) em tempo polinomial assumindo P = NP?

Por "honesto" e "realmente resolve", quero dizer que o algoritmo atende às definições clássicas de um algoritmo de tempo polinomial, ou seja, aqui devem existir constantes modo que, em qualquer entrada algoritmo, termine em não mais que pisa e "yes" se SUBSET-SUM e "no" caso contrário. O algoritmo da Wikipedia não atende à primeira condição e, portanto, não "resolve" realmente o problema.$C_1, C_2$$x$$C_1 \cdot |x|^{C_2}$$x \in$

Posso responder pela metade, mas acredito que a pergunta mais profunda que você está enfrentando é algo que estou aprendendo melhor :)

O algoritmo na wikipedia, chamado W, é baseado na idéia: em vez de adivinhar certificados, por que não adivinhar o próprio algoritmo P determinístico D? Isso é caro, mas, como é independente da entrada, é O (1) (se esse algoritmo existir). Na verdade, o algoritmo sempre decide mesmo se P! = NP, porque é claro que há uma série de programas de "força bruta" que imprimem apenas um certificado possível e interrompem, para que W possa voltar a uma força bruta muito lenta.

O problema é que você realmente não tem como verificar o programa que ele retorna para você. Você pode imaginar executando W e achar que parece preferir um determinado programa, mas pode descobrir que, em entradas maiores, ele eventualmente encontra uma falha nesse programa e segue em frente. Pode parecer um algoritmo que parece mas mais tarde encontra um erro nele e muda para um algoritmo . Você nunca saberá quando encontrou o "certo".$n^7$$n^{2000}$

Essa é realmente a mesma idéia usada na prova do teorema de Karp-Lipton: dado poder computacional suficiente, você pode usá-lo para começar a adivinhar classes inteiras de programas e verificar se eles funcionam (a prova é exatamente "adivinhe um programa e verifique se funciona e, em seguida, use-o ", o que requer um pouco de poder computacional - mais que o NP - para ser executado.)

Não conheço a teoria sobre o quão complicada pode ser uma solução, mas talvez alguém com mais conhecimento possa responder.

O cenário mais concreto na realidade P = NP é que alguém realmente constrói um algoritmo para qualquer problema completo de NP, como SAT.

Acho que você fez uma boa pergunta e estou curioso para preencher as lacunas da minha resposta, sobre como o W pode ser analisado e tornado mais útil na semi-prática.

Vou tentar uma resposta parcial para sua pergunta, mas acho que deve ser suficiente para sua busca.

Ser NP-completo recorre a ser NP E NP-DURO.

Ser NP-HARD significa que todos os problemas no NP podem ser traduzidos, através de uma transformação polinomial do tempo, nesse problema.

Sabe-se que o SSP é NP-HARD (e NP-COMPLETE).

Isso significa, por exemplo, que você pode procurar na Internet a transformação de Polinomial-Time específica que MOSTRA que o SSP é NP-HARD (em qualquer documento que o prove).

Essa transformação é um algoritmo "honesto", com garantia de execução em tempo polinomial e está escrita em algum artigo, em algum lugar. Vamos chamá-lo de 'SSP-T' (para transformação do SSP).

A única maneira de provar que P = NP é EXIBIR um algoritmo de tempo polinomial para um problema em NP.

Portanto, se você assumir que P = NP, estará assumindo que possui em suas próprias mãos um algoritmo de tempo polinomial "honesto" para resolver um problema de NP (qualquer um). Vamos chamar esse algoritmo: 'H'

Agora ... dado qualquer problema no NP, vamos chamá-lo de 'Meu-problema-NP' ...

A solução que você está procurando é:

• Aplique o SSP-T para transformá-lo em uma instância do SSP,

• Agora use o SSP-T novamente para transformar essa instância do SSP em uma instância do 'H' (o NP de um - qualquer um - problema que VOCÊ SABE resolver em P - com base no pressuposto de que P = NP-- ),

• Execute H para encontrar uma solução.

• Use o SSP-T para interpretar a solução no SSP

• Use o SSP-T mais uma vez para interpretar a solução em 'My-NP-problem' (o problema arbitrário que você queria resolver no começo).

E lá vai você!

Essas 5 etapas seqüenciais são o algoritmo "honesto" que você estava procurando.

Cada etapa é executada em tempo polinomial e é garantida a existência pela própria definição de cada conceito.

Você poderia ter escolhido qualquer outro problema NP-HARD, em vez do SSP, porque a definição de NP-HARD é a que garante (por definição!) Que:

• SSP-T existe,

• é um algoritmo,

• é bidirecional,

• é válido e aplica-se a qualquer problema de NP; e

• é executado em tempo polinomial

De fato, se você procurar a maneira mais comum de mostrar que qualquer problema é NP-HARD, é uma transformação no SAT-3, que foi um dos primeiros problemas a serem mostrados no NP-HARD (em algum momento nos anos 60/70).

Deixe-me saber de qualquer fraqueza que você possa encontrar no raciocínio / explicação que dei.