Assumindo p= NP, como seria uma resolver o problema de coloração do gráfico no tempo polinomial?

Question

Supondo que tenhamos $ \ sf p= NP $ , como eu mostraria como resolver o problema de coloração do gráfico no tempo polinomial?

Dado um gráfico $ g= (v, e) $ , encontre uma coloração válida $ \ chi (g): V \ to \ {1,2, \ cdots, k \} $ para alguma $ k $ satisfazendo a propriedade que $ (u, v) \ em e $ implica $ \ chi (u) \ ne \ chi (v) $ de modo aminimizar o menor número $ k $ de "cores".

Answer 1

Existem dois casos:

.

1. $ p= np $ não construtivamente: isso significa que derivamos uma contradição da suposição de que $ P \ neq np $ e, portanto, pode concluir que $ p= NP $ pela lei do meio excluído. Neste caso, temos Não ideia O que um algoritmo para resolver a coloração do gráfico em tempo polinomial parece, ou qualquer outro problema. Sabemos que existe, porque sabemos que, se não existir, podemos derivar uma contradição. Então uma prova desta forma é muito inútil para resolver problemas rapidamente.

2. $ p= NP $ construtivamente. Neste caso, temos um algoritmo de tempo polinomial para algumas $ NP $ - problema, digamos $ l $ . Se $ l $ é NP-Hard, então deve resolver algum outro problema NP-Hard no tempo polinomial (isto é, reduz desse problema). Esse problema, por sua vez, reduz de outro problema, ou tem uma redução direta de todos os problemas na $ NP $ . Continuamos seguindo a trilha das reduções até chegarmos a uma com uma prova direta (provavelmente 3,sat).

   Ao compor essas reduções, obtemos um algoritmo que resolve 3,sates no tempo polinomial (porque cada redução só faz um número polinomial de chamadas para o algoritmo anterior, e nosso algoritmo inicial para $ L $ é executado em tempo polinomial.

   Nós levamos esse algoritmo na redução de Cook-Levin Teorem , o que nos dá uma maneira de simular qualquer algoritmo em execução no tempo polinomial com um número polinomial de chamadas para um solucionador de 3sat. Novamente, um número polinomial de chamadas para um algoritmo de tempo polinômico é executado em tempo polinomial.

   Finalmente, há um algoritmo simples não determinístico que resolve a coloração de gráfico no tempo polinomial: basta adivinhar uma coloração e verificar se é válido. Então usamos o Cookin Levin para simular este algoritmo no tempo polinomial.

   Como você pode imaginar, cada vez que temos que compor uma redução, o grau de nosso polinômio vai ficar mais alto e mais alto. Por isso é inteiramente possível que $ p= NP $ Mas a coloração do gráfico só pode ser resolvida, digamos, $ O (n ^ {100000000000000}) $ tempo. Isso é ainda tempo polinomial, mas realmente não nos compra muito em termos de praticamente resolver problemas.

Answer 2

Se p= np, isso significa que há algum problema no NP, por exemplo, o problema "é $ g $ $ K $ -Colatable?", Onde $ g $ é um gráfico finito e $ K $ um inteiro, há um algoritmo para resolvê-lo em tempo polinomial.

Infelizmente, nosso problema não está no NP. Queremos encontrar uma $ k $ -colorização para o mínimo possível $ k $ . Agora podemos encontrar o mínimo possível $ k $ no tempo polinomial apenas resolvendo repetidamente o problema acima para $ k= 1, 2, \ ldots $ até retornar a resposta "Sim". (Note que isso acontece no momento $ k $ atinge o número de vértices, se não anteriormente, então apenas um número polinômico de instâncias é necessário.)

Mas agora que sabemos $ k $ , como encontramos uma $ k $ -coloring ? Bem, se $ k $ é igual ao número de vértices, isso é fácil: cada vértice deve ter uma cor diferente. Se $ k $ é menor que o número de vértices, em qualquer coloração (e sabemos que existe), há dois vértices $ x $ e $ y $ da mesma cor (que deve ser não adjacente). Isso significa que podemos combinar $ x $ e $ y $ (remova-os e substituí-los por um novo vértice que é adjacente a todos os vizinhos de $ x $ ou $ y $ ), e os mesmos funcionamentos de coloração para este novo gráfico. Então este novo gráfico também é $ k $ - coravelável e tem um pouco mais vértice.

Então, o que podemos fazer é correr sobre todos os pares de vértices não adjacentes $ x, y $ e verifique se o novo gráfico formado pela combinação $ x $ e $ y $ é $ k $ - Colocable, até obter uma resposta "sim" (isso deve eventualmente acontecer). Repetimos esse processo, mantendo o controle de quais vértices originais foram combinados para formar cada vértice atual, até que o gráfico tenha apenas $ k $ vértices. Isso divide os vértices do gráfico original em $ k $ conjuntos, e podemos apenas dar a cada definição sua própria cor para obter uma $ k $ -colorização de $ g $ .

Answer 3

o seguinte algoritmo aproximadamente esboçado, assumindo p= np, encontra uma coloração 3 do gráfico de entrada, se existir, no tempo polinomial. Se não houver tal 3 coloração, nunca termina.

Primeiro, aprenda a enumerar todos os algoritmos possíveis (máquinas de Turing) e simular computação de qualquer máquina de Turing na entrada arbitrária.

Segundo, aprenda a enumerar todos os algoritmos possíveis com um despertador de tempo em anexo. (Isso significa que estaremos enumerando um caso especial de máquinas de Turing que conceitualmente façam duas coisas em paralelo; em um conjunto de fitas, eles compõem o "principal problema", e em uma fita separada, eles apenas contam para zero de um fixo uma das funções n, 2 * n ^ 2, 3 * n ^ 3, onde n é o comprimento da entrada para o problema principal, interrompendo o cálculo (talvez prematuramente a partir da perspectiva do problema principal) uma vez Contagem regressiva na fita separada (chamada despertador) atinge zero antes que o problema principal seja resolvido. Portanto, às vezes, a computação é encerrada porque uma saída foi fornecida para o problema principal, e às vezes a computação é finalizada pelo despertador, com a saída fita contendo o que acontece.)

A ordem exata em que as máquinas de Turing com um despertador polinomial anexado são enumeradas devem ser exaustivas: Deve ser tal que encontraremos todas as combinações de uma máquina de Turing e de uma função de despertador entre as sugeridas acima mais cedo ou mais tarde.

Agora, aprenda a simular todas essas máquinas de Turing com um despertador polinomial anexo em paralelo, iniciá-los bem espaçados no tempo um por um. Em particular, certifique-se de que quase uma metade do tempo total de funcionamento é dedicada à primeira máquina de Turing com um despertador polinomial anexo na enumeração, quase um quarto do tempo total de funcionamento para a segunda máquina, quase um oitavo dele para o terceira máquina e assim por diante. (Estamos certificando-se de que cada máquina de Turing na enumeração recebe uma faixa de fração constante conhecida de tempo total de execução, assumindo que continuamos correndo pelo menos até a primeira transição.)

Como podemos fazer isso? Exemplo: simule uma transição da primeira máquina. Então o mesmo novamente - mais uma transição da primeira máquina. Então uma transição da segunda máquina. Do que tudo isso novamente: mais duas transições da primeira máquina e mais uma da segunda máquina. Só então faça a primeira transição da terceira máquina, seguida de tudo isso novamente (sete mais transições no total) antes de simular a primeira transição da quarta máquina.

De tempos em tempos, uma máquina termina, seja devido ao seu despertador ou a ter resolver seu problema principal (que raramente consistirá de uma produção de 3 corantes do gráfico de entrada, mas quem se importa). Se uma máquina terminou, verificamos se produziu uma coloração válida 3 do gráfico de entrada em sua fita de saída e, em caso afirmativo, terminamos toda a simulação de todas as máquinas Turing com despertadores anexados, retornando a mesma coloração que o saída.

Para ser honesto, não verifiquei de perto, posso amortizar a sobrecarga de trocar a atenção de uma máquina para uma máquina, a sobrecarga de iterating nas máquinas (ou seja, gerando o estado inicial de uma nova máquina na enumeração ), e a sobrecarga de verificar os estados do terminal (se uma máquina de terminação tropeçou em uma coloração válida 3 ou não); Mas certamente posso ter certeza de passar mais tempo nas transições simuladas de máquinas de Turing individuais do que em todos esses tipos de sobrecarga, isto é, a sobrecarga total acaba com menos de 100%, novamente um fator constante.

Agora, é bem sabido que a versão de função do 3 problema de coloração é autodutível para sua versão de decisão. Há um simples algoritmo de tempo polinomial para o problema de decisão (por p= NP) e, portanto, o algoritmo auto-reduzido que identifica de forma confiável um exemplo 3 coloração em tempo polinomial sempre que existe, ocorre em nossa enumeração De todas as máquinas de Turing - e ocorre em algum lugar mesmo com um despertador de tempo polinomial liberal liberal que permite completar em qualquer momento necessário. Boas notícias é que damos uma fração fixa de atenção (do recurso de tempo) a esta máquina específica em nossa simulação multitarefa, portanto nós diminuí-lo apenas por um fator constante (enorme) - pelas outras máquinas simultaneamente simuladas, e por os restantes até 100% de sobrecarga. Portanto, mesmo esta simulação "universal" específica é capaz de fornecer exemplos de 3 coloração no tempo polinomial. Quod erat Promissum.

===

(Eu adoraria dizer que essa simulação chega perto de preservar mesmo o expoente ideal de encontrar a cor 3, mas isso simplesmente não seria verdade. O maior problema a esse respeito é que o simulador "universal" pode tem menos fitas e menos estados que a máquina sendo simulada e simulando

Uma única transição é um exercício caro; A simulação preserva o tempo polinomial, mas não o expoente específico.)

Infelizmente, qualquer dessas simulações só se torna um algoritmo de tempo polinomial para encontrar 3 colores, se agora nós o equiparmos com seu próprio despertador de tempo polinômio (assim a diminuindo duas vezes, e também garantindo que ela termina em qualquer entrada dentro do limite de tempo); E este último passo é condutivo. Ao contrário de qualquer parte da construção até agora, não sabemos qual polinômio entre N, 2 * n ^ 2, 3 * n ^ 3, ... deve ser escolhido para o despertador. Apenas sabemos que existe um despertador suficientemente liberal, de tal forma que, se nós anexá-lo à nossa (outra máquina universal) "universal", obteremos um algoritmo de tempo polinomial fazendo 3 corantes onde quer que existam e rejeitando gráficos (somente) que não são 3 cores coloridas ou entradas que não codificam gráficos.

O método da simulação universal pode ser estendido até mesmo para o seu problema de colorir gráfico com a ajuda da técnica adicional descrita Nesta resposta . O que fica mais confuso é que não somos mais capazes de filtrar "respostas erradas" que facilmente; Se uma máquina nos oferecer uma coloração de 5, como sabemos se existe um 4-colorir? A solução suficiente é apenas esperar, ou uma 4-colorir aparecerá na saída de uma máquina infantil melhor comportada ou não, antes que o despertador mestre fique para fora. Mais uma vez, o último passo será não construtivo: sabemos que com um despertador de tempo polinômico suficientemente liberal, teríamos um algoritmo polinomial nos dando corantes ideais, mas é difícil dizer qual polinômio específico escolher se tudo o que sabemos é que P= np. Se escolhermos um despertador de tempo polinômico muito agressivo (insuficiente), não só nós às vezes não vamos encontrar a coloração ideal, mas às vezes vamos produzir uma coloração suboptimal que tentamos esperar, mas não o suficiente.

Answer 4

Ter p= np significa é um algoritmo de tempo polinomial.Isso não significa que nós sabemos um, ou nós nunca saber um, ou nós seremos capazes de provar que é executado em tempo polinomial.

e podemos encontrar que há um algoritmo em execução em O (n ^ 10000), o que significa que podemos realmente resolver sem instâncias de tamanho> 1 .