O que é "P = NP?", E por que é uma pergunta tão famosa? [fechadas]

A questão de saber se P = NP é talvez o mais famoso de toda a Ciência da Computação. O que isso significa? E por que isso é tão interessante?

Ah, e para crédito extra, envie uma prova da verdade ou falsidade da declaração. :)

P significa tempo polinomial. NP significa tempo polinomial não determinístico.

Definições:

• Tempo polinomial significa que a complexidade do algoritmo é O (n ^ k), onde n é o tamanho dos seus dados (por exemplo, número de elementos em uma lista a ser classificada) ek é uma constante.

• Complexidade é o tempo medido no número de operações necessárias, em função do número de itens de dados.

• A operação é o que faz sentido como uma operação básica para uma tarefa específica. Para classificação, a operação básica é uma comparação. Para multiplicação de matrizes, a operação básica é multiplicação de dois números.

Agora, a pergunta é: o que significa determinístico versus não determinístico? Existe um modelo computacional abstrato, um computador imaginário chamado máquina de Turing (TM). Esta máquina possui um número finito de estados e uma fita infinita, que possui células discretas nas quais um conjunto finito de símbolos pode ser escrito e lido. A qualquer momento, a TM está em um de seus estados e está observando uma célula específica na fita. Dependendo do que é lido nessa célula, ele pode gravar um novo símbolo nessa célula, mover a fita uma célula para frente ou para trás e entrar em um estado diferente. Isso é chamado de transição de estado. Surpreendentemente, construindo cuidadosamente estados e transições, você pode criar uma TM, equivalente a qualquer programa de computador que possa ser gravado.

Existem dois tipos de MTs que nos interessam aqui: determinístico e não determinístico. Uma TM determinística tem apenas uma transição de cada estado para cada símbolo que está lendo na fita. Uma MT não determinística pode ter várias dessas transições, ou seja, é capaz de verificar várias possibilidades simultaneamente. É como gerar vários threads. A diferença é que uma TM não determinística pode gerar tantos "threads" quantos desejar, enquanto em um computador real apenas um número específico de threads pode ser executado por vez (igual ao número de CPUs). Na realidade, os computadores são basicamente MTs determinísticas com fitas finitas. Por outro lado, uma MT não determinística não pode ser realizada fisicamente, exceto talvez com um computador quântico.

Está provado que qualquer problema que possa ser resolvido por uma MT não determinística pode ser resolvido por uma MT determinística. No entanto, não está claro quanto tempo levará. A afirmação P = NP significa que, se um problema leva tempo polinomial em uma MT não determinística, pode-se construir uma MT determinística que resolveria o mesmo problema também no tempo polinomial. Até agora ninguém foi capaz de mostrar que isso pode ser feito, mas ninguém foi capaz de provar que também não pode ser feito.

Problema NP completo significa um problema NP X, de modo que qualquer problema NP Y possa ser reduzido a X por uma redução polinomial. Isso implica que, se alguém tiver uma solução em tempo polinomial para um problema de NP completo, isso também fornecerá uma solução em tempo polinomial para qualquer problema de NP. Assim, isso provaria que P = NP. Por outro lado, se alguém provar que P! = NP, estaremos certos de que não há como resolver um problema de PN em tempo polinomial em um computador convencional.

Um exemplo de um problema de NP-completo é o problema de encontrar uma atribuição de verdade que tornaria verdadeira uma expressão booleana contendo n variáveis.
No momento, na prática, qualquer problema que leve tempo polinomial na MT não determinística só pode ser feito em tempo exponencial em uma MT determinística ou em um computador convencional.
Por exemplo, a única maneira de resolver o problema da atribuição da verdade é tentar 2 ^ n possibilidades.

1. Um problema de sim ou não está em P ( tempo olinomial P ) se a resposta puder ser calculada em tempo polinomial.
2. Um sim ou não é problema em NP ( N on-determinística P tempo olynomial) se uma resposta sim pode ser verificada em tempo polinomial.

Intuitivamente, podemos ver que, se um problema está em P , então está em NP . Dada uma resposta potencial para um problema em P , podemos verificar a resposta simplesmente recalculando a resposta.

Menos óbvio, e muito mais difícil de responder, é se todos os problemas em NP estão em P . O fato de podermos verificar uma resposta no tempo polinomial significa que podemos calcular essa resposta no tempo polinomial?

Há um grande número de problemas importantes que se sabe serem NP- completos (basicamente, se algum desses problemas estiver em P , então todos os problemas em NP estarão em P ). Se P = NP , todos esses problemas terão uma solução eficiente (tempo polinomial).

A maioria dos cientistas acredita que P ! = NP . No entanto, nenhuma prova foi ainda estabelecida para P = NP ou P ! = NP . Se alguém fornecer uma prova para qualquer uma das conjecturas, ganhará US $ 1 milhão .

Para dar a resposta mais simples, posso pensar em:

Suponha que tenhamos um problema que consiga um certo número de entradas e possua várias soluções em potencial, que podem ou não resolver o problema de determinadas entradas. Um quebra-cabeça lógico em uma revista de quebra-cabeças seria um bom exemplo: as entradas são as condições ("George não mora na casa azul ou verde"), e a solução potencial é uma lista de declarações ("George mora no amarelo casa, cultiva ervilhas e é dono do cachorro "). Um exemplo famoso é o problema do Vendedor ambulante: dada uma lista de cidades e os horários de deslocamento de qualquer cidade para outra, além de um limite de tempo, uma solução em potencial seria uma lista de cidades na ordem em que o vendedor as visita e funcionaria se a soma dos tempos de viagem fosse menor que o limite de tempo.

Esse problema está no NP se pudermos verificar com eficiência uma solução em potencial para ver se ela funciona. Por exemplo, dada uma lista de cidades para o vendedor visitar em ordem, podemos adicionar os horários de cada viagem entre cidades e ver facilmente se está abaixo do limite de tempo. Um problema está em P se pudermos encontrar com eficiência uma solução, se houver.

(Eficientemente, aqui, tem um significado matemático preciso. Na prática, significa que grandes problemas não são excessivamente difíceis de resolver. Ao procurar uma solução possível, uma maneira ineficiente seria listar todas as possíveis soluções possíveis ou algo próximo disso. , embora uma maneira eficiente exija a pesquisa de um conjunto muito mais limitado.)

Portanto, o problema P = NP pode ser expresso da seguinte maneira: Se você pode verificar uma solução para um problema do tipo descrito acima com eficiência, pode encontrar uma solução (ou provar que não existe) com eficiência? A resposta óbvia é "Por que você deveria ser capaz?", E é aí que está o problema hoje. Ninguém foi capaz de provar isso de uma maneira ou de outra, e isso incomoda muitos matemáticos e cientistas da computação. É por isso que qualquer pessoa que possa provar a solução recebe um milhão de dólares da Claypool Foundation.

Geralmente assumimos que P não é igual a NP, que não há uma maneira geral de encontrar soluções. Se descobrisse que P = NP, muitas coisas mudariam. Por exemplo, a criptografia se tornaria impossível e, com ela, qualquer tipo de privacidade ou verificabilidade na Internet. Afinal, podemos pegar com eficiência o texto criptografado e a chave e produzir o texto original; portanto, se P = NP, poderíamos encontrar com eficiência a chave sem conhecê-la de antemão. A quebra de senha se tornaria trivial. Por outro lado, existem classes inteiras de problemas de planejamento e problemas de alocação de recursos que poderíamos resolver de maneira eficaz.

Você pode ter ouvido a descrição NP-complete. Um problema NP completo é aquele que é NP (é claro), e possui essa propriedade interessante: se estiver em P, todo problema de NP é e, portanto, P = NP. Se você pudesse encontrar uma maneira de resolver com eficiência o problema do Vendedor Viajante ou quebra-cabeças lógicos de revistas de quebra-cabeças, poderia resolver com eficiência qualquer coisa no NP. Um problema NP-completo é, de certa forma, o tipo mais difícil de NP.

Portanto, se você puder encontrar uma técnica de solução geral eficiente para qualquer problema completo de NP ou provar que não existe, fama e fortuna são suas.

Um breve resumo do meu humilde conhecimento:

Existem alguns problemas computacionais fáceis (como encontrar o caminho mais curto entre dois pontos em um gráfico), que podem ser calculados rapidamente (O (n ^ k), onde n é o tamanho da entrada e k é uma constante (no caso de gráficos, é o número de vértices ou arestas)).

Outros problemas, como encontrar um caminho que cruze todos os vértices de um gráfico ou obter a chave privada RSA da chave pública são mais difíceis (O (e ^ n)).

Mas o CS speak diz que o problema é que não podemos 'converter' uma máquina de Turing não determinística para uma determinística, mas podemos transformar autômatos finitos não determinísticos (como o analisador de expressões regulares) em determinísticos (bem, você pode, mas o tempo de execução da máquina vai demorar). Ou seja, temos que tentar todos os caminhos possíveis (geralmente professores inteligentes de CS podem excluir alguns).

É interessante porque ninguém sequer tem idéia da solução. Alguns dizem que é verdade, outros dizem que é falso, mas não há consenso. Outra coisa interessante é que uma solução seria prejudicial para criptografia de chave pública / privada (como RSA). Você pode quebrá-los tão facilmente quanto gerar uma chave RSA agora.

E é um problema bastante inspirador.

Não há muito a acrescentar ao que e por que da parte P =? NP da pergunta, mas no que diz respeito à prova. Não apenas uma prova valeria algum crédito extra, mas resolveria um dos problemas do milênio . Uma pesquisa interessante foi realizada recentemente e vale a pena ler os resultados publicados (PDF) em relação ao assunto de uma prova.

Primeiro, algumas definições:

• Um problema específico está em P se você puder calcular uma solução em tempo menor do que n^kpara alguns k, onde nestá o tamanho da entrada. Por exemplo, a classificação pode ser feita em n log num valor menor que n^2, portanto, a classificação é um tempo polinomial.

• Um problema está no NP se existir um kque exista uma solução de tamanho no máximo n^kque você possa verificar a tempo n^k. Tome 3 cores de gráficos: dado um gráfico, uma cor 3 é uma lista de pares (vértice, cor) que têm tamanho O(n)e você pode verificar com o tempo O(m)(ou O(n^2)) se todos os vizinhos têm cores diferentes. Portanto, um gráfico é tricolor apenas se houver uma solução curta e facilmente verificável.

Uma definição equivalente de NP é "problemas que podem ser resolvidos por um N máquina de Turing ondeterministic em P tempo olynomial". Embora isso indique de onde vem o nome, ele não fornece a mesma sensação intuitiva de como são os problemas de NP.

Observe que P é um subconjunto de NP: se você pode encontrar uma solução em tempo polinomial, existe uma solução que pode ser verificada em tempo polinomial - basta verificar se a solução fornecida é igual à que você pode encontrar.

Por que a pergunta é P =? NPinteressante? Para responder a isso, é preciso primeiro ver quais são os problemas de NP-completos. Simplificando,

• Um problema L está NP completo se (1) L estiver em P e (2) um algoritmo que resolve L pode ser usado para resolver qualquer problema L 'em NP; isto é, dada uma instância de L ', você pode criar uma instância de L que tenha uma solução se e somente se a instância de L' tiver uma solução. Formalmente falando, todo problema L 'em NP é redutível a L.

Observe que a instância de L deve ser computável em tempo polinomial e ter tamanho polinomial, no tamanho de L '; dessa forma, resolver um problema completo de NP em tempo polinomial nos fornece uma solução de tempo polinomial para todos os problemas de NP.

Aqui está um exemplo: suponha que sabemos que 3 cores para gráficos é um problema difícil de NP. Queremos provar que a decisão da satisfação de fórmulas booleanas também é um problema difícil de NP.

Para cada vértice v, tenha duas variáveis ​​booleanas v_h e v_l e o requisito (v_h ou v_l): cada par pode ter apenas os valores {01, 10, 11}, que podemos considerar as cores 1, 2 e 3.

Para cada aresta (u, v), é necessário que (u_h, u_l)! = (V_h, v_l). Isso é,

not ((u_h and not u_l) and (v_h and not v_l) or ...) enumerando todas as configurações e estipulações iguais de que nenhuma delas é o caso.

ANDA união de todas essas restrições fornece uma fórmula booleana que possui tamanho polinomial ( O(n+m)). Você também pode verificar se leva um tempo polinomial para calcular: você está fazendo O(1)coisas diretas por vértice e por aresta.

Se você puder resolver a fórmula booleana que criei, também poderá resolver a coloração gráfica: para cada par de variáveis ​​v_h e v_l, deixe a cor de v ser a que corresponde aos valores dessas variáveis. Pela construção da fórmula, os vizinhos não terão cores iguais.

Portanto, se a coloração de três gráficos é NP-completa, o mesmo ocorre com a satisfação da fórmula booleana.

Sabemos que a coloração de 3 gráficos é NP-completa; no entanto, historicamente, chegamos a saber que, primeiro mostrando a completude NP da satisfação do circuito booleano e, depois, reduzindo-a à 3-colorabilidade (em vez do contrário).