Minha pergunta é a seguinte. Assuma issoΠΠ\Pié um problema difícil de NP. Dada uma instância arbitráriaIII do ΠΠ\Pi e suponha que um adversário sabe que essa instância é fácil de resolver, é possível encontrar um algoritmo determinístico de tempo polinomial para resolver essa instância específica...
Recentemente, pensei na seguinte prova de que L = P implica P = NP. Suponha que L = P. Seja A um problema no NP. Pela definição do verificador de NP, cada solução positiva para A tem uma testemunha que pode ser verificada em tempo polinomial. Desde P = L, a mesma solução pode ser verificada no...
Tenho certeza de que deve haver algo errado com o seguinte raciocínio, porque, caso contrário, muitas pesquisas de P vs. NP seriam reduzidas, mas não consigo determinar meu erro: Para qualquer número inteiro fixo k>0k>0k>0 definir Bk:={⟨φ⟩|φis a wff of ZF and has a proof of...
No livro de Lance Fortnow, The Golden Ticket , ele menciona que uma vez que você tenha um algoritmo de tempo polinomial para um problema completo de NP, poderá usá-lo para encontrar um algoritmo mais rápido. Você pode me dizer como isso é feito? E uma vez feito isso, você pode usar o novo algoritmo...
O Concorde TSP é um solucionador de TSP. Os solucionadores SAT são solucionadores de satisfação booleana. TSP e SAT são NP-completos. Por isso, por que dedicar tempo ao desenvolvimento do Concorde TSP quando há uma abundância de solucionadores SAT no mercado naquela
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...