O que é “P = NP?”, E por que é uma pergunta tão famoso? [fechadas]

Question

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 é tão interessante?

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

Answer 1

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 dados (por exemplo, número de elementos na lista a ser classificados) e k é uma constante.

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

• Operação é o que faz sentido como uma operação básica para uma determinada tarefa. Para classificar a operação básica é uma comparação. Para multiplicação de matrizes a operação básica é a multiplicação de dois números.

Agora, a questão é, o que faz determinista vs. média não-determinista. Há um modelo computacional abstrato, um computador imaginário chamado uma máquina de Turing (TM). Esta máquina tem um número finito de estados, e uma fita infinita, que tem células discretos em que um conjunto finito de símbolos podem ser escritos e lidos. Em um determinado momento, a TM está em um de seus estados, e ele está olhando para uma célula em particular na fita. Dependendo do que ele lê a partir dessa célula, pode escrever um novo símbolo para essa célula, mover a célula uma fita para a 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 um TM, o que equivale a qualquer programa de computador que pode ser escrito. É por isso que ele é usado como um modelo teórico para provar coisas sobre o que os computadores podem e não podem fazer.

Existem dois tipos de TM é que nós aqui preocupação: determinista e não-determinístico. A TM determinista tem apenas uma transição de cada estado para cada símbolo que está lendo a fita. Um TM não-determinística pode ter vários tal transição, i. e. ele é capaz de verificar várias possibilidades simultaneamente. Esta é uma espécie de desova vários segmentos. A diferença é que a TM não-determinística pode gerar o maior número de tais "linhas" como ele quer, ao mesmo tempo em um computador real somente um número específico de threads pode ser executado em um momento (igual ao número de CPUs). Na realidade, os computadores são basicamente TMs determinista com fitas finitas. Por outro lado, a TM não-determinística não pode ser fisicamente realizadas, exceto talvez com um computador quântico.

Está provado que qualquer problema que pode ser resolvido por uma TM não-determinística pode ser resolvido por uma TM determinista. No entanto, não está claro quanto tempo vai demorar. O meio NP que se um problema leva tempo polinomial em uma TM não-determinística, então pode-se construir uma TM determinista que iria resolver o mesmo problema também em tempo polinomial declaração P =. Até agora ninguém ter sido capaz de mostrar que pode ser feito, mas ninguém foi capaz de provar que não pode ser feito, também.

meios problema NP-NP completa um problema X, de tal modo que qualquer problema NP Y pode ser reduzido para X por uma redução polinomial. Isso implica que se alguém surge com uma solução em tempo polinomial para um problema NP-completo, que irá também dar uma solução polinomial tempo para qualquer problema NP. Assim que se provar que P = NP. Por outro lado, se alguém viesse a provar que P! = NP, então poderíamos estar certos de que não há nenhuma maneira de resolver um problema NP em tempo polinomial em um computador convencional.

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

Answer 2

1. Um sim ou não há problema está em P ( P tempo olynomial) se a resposta pode ser calculado em tempo polinomial.
2. Um sim ou não há problema é em NP ( N no-determinística P tempo olynomial) se uma resposta sim pode ser < em> Verificado em tempo polinomial.

Intuitivamente, podemos ver que se um problema está em P , então ele está em NP . Dada a potencial resposta para um problema em P , podemos verificar a resposta, basta recalcular a resposta.

Menos óbvio, e muito mais difícil de responder, é se todos os problemas em NP está em P . Será que o fato de que podemos verificar uma resposta em tempo médio de polinômio que podemos calcular essa resposta em tempo polinomial?

Há um grande número de problemas importantes que são conhecidos por ser NP -completo (basicamente, se nenhum destes problemas são provou ser em P , em seguida, todas NP problemas são provou ser em P ). Se P = NP , em seguida, todos esses problemas serão provado ter uma solução eficiente (tempo polinomial).

A maioria dos cientistas acreditam que P ! = NP . No entanto, nenhuma prova foi ainda estabelecida para qualquer P = NP ou P ! = NP . Se alguém fornece uma prova para qualquer conjectura, eles vão ganhar $ 1 milhões de EUA.

Answer 3

Para dar a resposta mais simples que posso pensar:

Suponha que temos um problema que leva um certo número de entradas, e tem várias soluções potenciais, que pode ou não pode resolver o problema para as entradas dadas. Um quebra-cabeça de lógica em uma revista de quebra-cabeça seria um bom exemplo: as entradas são as condições ( "George não vive na casa azul ou verde"), e a solução potencial é uma lista de instruções ( "George vive no amarelo casa, cresce ervilhas, e é dono do cão "). Um exemplo famoso é o problema do caixeiro viajante: dada uma lista de cidades, e as vezes para começar a partir de qualquer cidade a qualquer outro, e um limite de tempo, uma solução potencial seria uma lista de cidades na ordem das visitas vendedor eles, e ele iria trabalhar, se a soma dos tempos de viagem foi menor do que o limite de tempo.

problema Tal está em NP se pode verificar de forma eficiente uma solução potencial para ver se funciona. Por exemplo, dada uma lista de cidades para o vendedor a visita em ordem, podemos somar os tempos para cada viagem entre as cidades, e facilmente ver se ele está abaixo do limite de tempo. Um problema está em P se pode eficientemente encontrar uma solução, se houver.

(com eficiência, aqui, tem um significado matemático preciso. Praticamente, isso 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 potenciais, ou algo perto de que, apesar de uma maneira eficiente exigiria pesquisando um conjunto muito mais limitado.)

Portanto, o problema NP P = pode ser expresso da seguinte maneira: Se você pode verificar uma solução para um problema do tipo descrito acima de forma eficiente, você pode encontrar uma solução (ou provar que não é nenhum) de forma eficiente? A resposta óbvia é "Por que você deve ser capaz de?", E isso é muito bonito, onde a matéria está hoje. Ninguém foi capaz de provar isso de uma maneira ou de outra, e que incomoda um monte de matemáticos e cientistas da computação. É por isso que qualquer um que pode provar a solução é para um milhão de dólares a partir do Claypool Foundation.

Nós geralmente assumem que P não é igual NP, que não há nenhuma maneira geral para encontrar soluções. Se descobriu-se que P = NP, um monte de coisas mudariam. Por exemplo, a criptografia se tornaria impossível, e com ele qualquer tipo de privacidade ou verificabilidade na Internet. Afinal, nós pode eficientemente tomar o texto criptografado ea chave e produzir o texto original, por isso, se P = NP poderíamos eficientemente encontrar a chave sem saber de antemão. Quebra de senha se tornaria trivial. Por outro lado, há classes inteiras de problemas de planejamento e problemas de alocação de recursos que poderia resolver de forma eficaz.

Você pode ter ouvido a descrição NP-completos. Um problema NP-completo é aquele que é NP (é claro), e tem essa propriedade interessante: se ele está em P, todo problema NP é, e assim P = NP. Se você pudesse encontrar uma maneira de resolver eficientemente o problema do caixeiro viajante, ou enigmas de lógica de revistas de quebra-cabeça, você pode eficientemente resolver nada em NP. problema um NP-complete é, de certa forma, o problema mais difícil tipo de NP.

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

Answer 4

Um breve resumo do meu humilde conhecimento:

Existem alguns problemas computacionais simples (como encontrar o caminho mais curto entre dois pontos num gráfico), que podem ser calculados bastante rápido (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 atravessa todos os vértices de um gráfico ou obter a chave privada RSA de chave pública é mais difícil (O (e ^ n)).

Mas CS falar diz que o problema é que não podemos 'converter' um não-determinístico Turing-máquina para um determinista, podemos, no entanto, transformar autômatos não-deterministas finitos (como o analisador regex) para os deterministas ( bem, você pode, mas o tempo de execução da máquina vai demorar muito). Isto é, temos que tentar todos os caminhos possíveis (normalmente professores CS inteligentes podem excluir alguns mais).

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

E é um problema bastante inspirador.

Answer 5

Não há muito que eu possa acrescentar ao que e por que da P =? NP parte da pergunta, mas no que diz respeito à prova. Não só seria uma prova valer a pena algum crédito extra, mas que iria resolver um dos Millennium Problemas . Uma pesquisa interessante foi recentemente conduzido eo resultados publicados (PDF) são definitivamente vale a pena ler em relação ao objecto de uma prova.

Answer 6

Em primeiro lugar, algumas definições:

• Um problema em particular está em P se você pode calcular uma solução em menos de n^k por algum k, onde n é o tamanho da entrada. Por exemplo, a triagem pode ser feito em n log n que é menos de n^2, então a classificação é tempo polinomial.

• Um problema está em NP se existe uma k tal que existe uma solução de tamanho no máximo n^k que você pode verificar no tempo, no máximo n^k. Tome 3-coloração de grafos: dado um gráfico, uma 3-coloração é uma lista de pares (vértice, cor), que tem o tamanho O(n) e você pode verificar em O(m) tempo (ou O(n^2)) se todos os vizinhos têm cores diferentes. Assim, um gráfico que representa apenas 3-ilusório se não é uma solução a curto 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". Enquanto que informa que o nome vem, ele não lhe dá a mesma sensação intuitiva do que problemas NP são como.

Note que P é um subconjunto de NP: se você pode encontrar uma solução em tempo polinomial, há uma solução que pode ser verificado em tempo polinomial - basta verificar que a solução dada é igual ao que você pode encontrar.

Por que a interessante questão P =? NP? Para responder a isso, é preciso primeiro ver o que problemas NP-completos são. Simplificando,

• Um problema L é NP-se completa (1) em que L é P, e (2) um algoritmo que resolve L pode ser utilizado para resolver qualquer problema L' em NP; isto é, dada uma instância de L 'você pode criar uma instância de L que tem uma solução se e somente se a instância do L' tem uma solução. Formalmente, cada problema L' em NP é redutível para L.

Note que a instância de L deve ser polinomial-time computável e tem tamanho polinomial, no tamanho de L '; dessa forma, resolvendo um problema NP-completos em tempo polinomial nos dá uma solução em tempo polinomial a todas problemas NP.

Aqui está um exemplo: suponha que nós sabemos que 3-coloração de grafos é um problema NP-hard. Queremos provar que decidir a satisfatibilidade das fórmulas booleanas é um problema NP-hard também.

Para cada vértice v, tem duas variáveis ??booleanas v_h e v_l, ea exigência (v_h ou v_l): cada par só pode ter os valores {01, 10, 11}, que podemos pensar como cor 1, 2 e 3.

Para cada aresta (u, v), tem a exigência de que (u_h, u_l)! = (V_h, v_l). Ou seja,

not ((u_h and not u_l) and (v_h and not v_l) or ...) enumerando todas as configurações e estipulação iguais que nenhum deles são o caso.

AND'ing juntos todos estes constrangimentos dá uma fórmula booleana que tem tamanho polinomial (O(n+m)). Você pode verificar que leva tempo polinomial para computação, bem como:. Você está fazendo coisas O(1) simples por vértice e por aresta

Se você pode resolver a fórmula booleana que eu fiz, então você também pode resolver gráfico colorir: para cada par de variáveis ??v_h e v_l, deixe a cor do v ser o único combinando os valores dessas variáveis. Pela construção da fórmula, os vizinhos não têm cores iguais.

Por isso, se 3-coloração de gráficos é NP-completo, então é booleano-fórmula-satisfazibilidade.

Sabemos que 3-coloração de grafos é NP-completos; No entanto, historicamente temos vindo a saber que por primeiro mostrando o NP-completude de boolean-circuit-satisfiability, e em seguida, reduzindo que a 3 de coloração (em vez do contrário).