P versus NP problem
comentada em 04/05/2021 07:06

É algo que vi em Ciência da Computação e que só sei o seguinte: os problemas NP complexos, na verdade, são NP escrotos de resolver.


InformaçãoPai_Naldo24 posts

Esse vídeo explica de uma forma bem didática.

Problemas em P são simples de encontrar a solução, e também simples de checar se a solução está correta. Exemplo: multiplicação de números. Multiplicar um número de 2 dígitos por outro é fácil, você levaria menos de um minuto. Fazer o mesmo para um número de 20 dígitos não é muito mais complexo, talvez você leve alguns minutos, mas há uma maneira simples de resolver o problema seguindo um algoritmo.

Problemas em NP são difíceis de encontrar a solução, porém ainda simples de checar se a solução está correta. Exemplo: colocar N rainhas em um tabuleiro de NxN sem elas se atacarem. No exemplo tradicional de 8 rainhas, você pode levar um certo tempo, mas há diversas soluções possíveis. E é fácil ver que a solução está correta, uma vez que você a apresente. Já se eu pedir para você fazer o mesmo em um tabuleiro de 80x80, colocando 80 rainhas sem se atacar, você provavelmente não conseguirá resolver nem mesmo com um computador. Esse é um problema difícil. Mas ao mostrar a solução, você rapidamente poderá verificar se é válida ou não.

A grande questão é saber se P = NP ou não. Se for equivalente, então quer dizer que existem algoritmos mais simples para resolver esses problemas difíceis, nós é que ainda não encontramos um. A corrente majoritária acha que P != NP, porém ainda não há provas.

@Bastter, talvez porque o prêmio para resolver esse problema é de US$ 1.000.000,00 (um milhão de dólares). 

Talvez porque se provarem que P = NP a Internet ficará menos segura e o bitcoin despencará (sabem dizer o porquê? Fica como dever de casa)

@rjuliano
Seria porque a "mineração" do bitcoin é um problema matemático dificílimo. Se de repente ficar fácil, já era. é isso?

@rjuliano até eu que sou burro entendi! achei massa.

Estou meio ocupado tentando comprovar as equações de Navier–Stokes. Sobrando um tempo vejo isso aí.

Um professor, da universidade daqui da cidade, disse ter achado a solução de PxNP. Ele montou uma apresentação, quase um congresso, onde mostraria a demonstração. Na hora que estava apresentado, encontrou um erro. Ele largou tudo e saiu desolado.

@faceless tem que respeitar a pessoa que reconhece o próprio erro.

@Lcrs com certeza!

42

All I know is that @Giovanni needs this shirt

@rjuliano Exatamente. Esse é um dos sete problemas matemáticos do milênio (nunca me esqueço do Russo que resolveu um deles e não quis saber nem do prêmio nem da fama):

Problemas do Prémio Millennium – Wikipédia, a enciclopédia livre

Matemático russo recusa prêmio de US$ 1 milhão - BBC News Brasil

Bitcoin e tudo o que depende de criptografia iria para o saco.

.

@O.Escolhido @rjuliano os computadores quânticos que estão sendo projetados não resolveriam estes problemas (e possivelmente causariam um colapso total)?

@Fernando_aprendiz Os algoritmos de criptografia teriam que ser alterados para outros que são "quantum-proof":

Post-quantum cryptography - Wikipedia

@O.Escolhido Interessante, obrigado por compartilhar!

NP = Problemas que levam um tempo não polinomial, não determinístico

P = Problemas que levam um tempo polinomial.

Ex:

Dada uma lista, pegar cada elemento da lista e comparar com outra lista, para ver se uma lista contém a outra.

Isso é um problema P, que pode ser resolvido em um tempo polinomial.

Por ex, o código abaixo compara 2 listas e checa se todos os elementos de lista 1 estão em lista 2, na mesma ordem:

bool checarSeAsListasSaoIguais(List<string> lista1, List<string> lista2) {
for(int i=0; i < sizeof(lista1); i++)
       if (lista1[i] != lista2[j]) return false;
return true;
}

Esse é um código o(n), o que significa que seu tempo de execução é "n" vezes o tamanho da lista, vezes o tempo de processamento para 1 if, + tempo de processamento do looping. 

Ou seja, ele é proporcional ao tamanho da lista por um fator de 1 para 1.


Agora o código abaixo faz a mesma coisa, mas lista1 pode ser menor que lista2, e os elementos não precisam estar em ordem. Se todos os elementos de lista1 estiverem em lista2, então o código retorna "verdadeiro":

bool elementoExisteNaLista(string elemento, List<string> lista) {
    for(int i=0; i < sizeof(lista1); i++)
       if (lista1[i] == elemento ) return true;
    return false;
}

bool checarSeAsListasSaoIguais(List<string> lista1, List<string> lista2) {
    for(int i=0; i < sizeof(lista1); i++)
         if (!elementoExisteNaLista(lista1[i], lista2))
             return false;
    return true;
}

Esse código é o(n²)

O que significa que o tempo de execução dele aumenta com o quadrado do tamanho dos dados. É um código menos "eficiente", mais lento, mais ainda assim de tempo de execução PREVISÍVEL.

Agora imagine um problema de otimização clássico, o caixeiro viajante:

Você tem n cidades e precisa traçar uma rota pro caixeiro percorrer todas essas cidades na menor distância possível, visitando cada uma delas 1 única vez. 

Esse problema é NP. O tempo de solução do algoritmo pode explodir. Por ex, se são só 2 cidades, é fácil, se são 10 cidades, o tempo de execução deixa de ser 5x maior e passa a ser um número não determinado de vezes maior. Com um certo número de cidades, o tempo de execução pode ser infinito... 

@FlyCavok se alguma criança de 7 anos entender isso ai eu meu nome é Kleytton (com dois tês)

@Giovanni ajuda a entender melhor isso estudando sobre Big O notation, ou análise de complexidade de algoritmos por tempo de execução. 

Foi mal, vou me esforçar melhor pra explicar sem tantos jargões. Explicar teoria da computação é difícil !!

em resumo, um problema P é aquele que você é capaz de escrever um algoritmo pra resolvê-lo e é capaz de descrever o quão “pesado” ele vai ser, utilizando a notação o(?), onde ? É um polinômio.

O(n) é um looping
o(n2) é um looping dentro de outro.
o(1) é uma execução “banal”

um problema NP é aquele que voce não consegue escrever um algoritmo que execute em um tempo previsível.

Nao estou dizendo que ele vai demorar. Um algoritmo NP pode ser rápido sim, mas pode, do nada, demorar infinitamente. Não há como prever. 

Isso torna tudo muito complexo, por que você escreve um código e não sabe se ele vai funcionar bem pra todos os casos.

Em resumo é isso 

Em teoria da computação existem problemas C e NC também.

C são os problemas computáveis. NC os não computáveis.

um problema não computável não pode ser resolvido por um computador.

Sim, eles existem hehehehe 

e não, não é por que o computador não é rápido o suficiente. Um problema NC precisa de outra máquina, outro modelo, que não seja o computador.

Um gráfico que ajuda a visualizar a complexidade dos algoritmos

Aqui tem mais informação sobre: bigocheatsheet.com
Ver mais

@FlyCavok

Fui googlar e tem os parcialmente computáveis tb..