Achei interessante um email de resposta do prof. Jorge Stolfi da Unicamp a cerca da questão P = NP
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/stolfi-on-NPcomplete.html
Se alguém conseguir provar que P é realmente NP, então é possível encontrar os fatores primos de um número em tempo polinomial. Isso, em tese, traria sérios problema pra algoritmos de criptografia baseados neste problema, como o RSA. Digo em tese por que, provar que existe e descobir um exemplar são coisas bem diferentes.
Então, as implicações práticas (práticas mesmo) depois da prova ou da refutação da igualdade acima são bem limitadas. Concordam?
Pensei que fóssemos estudar classes de problemas nesta matéria.
Sei que amanhã tem prova. Se quiserem deixar comentários pode ser depois.
Abrç
Também pensei... =/
Não existe uma disciplina (MAC430) que cuida disso? Aliás, nunca vi ela sendo oferecida.
---tempo---
Acabei de ver que ela foi oferecida em 2008. =P
---tempo---
Acabei de ver que ela foi oferecida em 2008. =P
Em edições anteriores de MAC0338
eu tentei falar de P = NP.
Mas, com o pouco tempo disponível,
a coisa ficou tão superficial e "chutada"
que eu achei melhor não falar do assunto
desta vez.
Há outras disciplinas onde o assunto
pode ser discutido de maneira bem mais
confortável.
eu tentei falar de P = NP.
Mas, com o pouco tempo disponível,
a coisa ficou tão superficial e "chutada"
que eu achei melhor não falar do assunto
desta vez.
Há outras disciplinas onde o assunto
pode ser discutido de maneira bem mais
confortável.
Fica desde já o pedido pelo oferecimento dessas disciplinas. 
Eu tinha escrito uma resposta super comprida e bem estruturada mas aí o PACA ficou malvado e apagou tudo. Acho que vamos ter que nos contentar com a versão "boca-suja", então.
P vs NP é uma questão fundamental e central em ciência da computação. Como diria o pessoal da Mastercard, uma prova de P vs NP não tem preço.
Esse o papo de se os algoritmos polinomiais realmente são rápidos só importa se você está fazendo afirmações sensacionalistas como essas de criptografia de banco*. O problema P vs NP é muito mais do que só isso, e dizer que uma prova pode ser limitada só porque o algoritmo pode ter que ser super lerdo é algo completamente míope.
*sem contar que fatorar inteiros nem é NP-completo, deviam pelo menos dar de exemplo um problema NP-completo de verdade, como o do cacheiro viajante :P
(Ok, ninguém provou se fatorar é NP-completo ou não ainda, mas como esse problema está tanto em NP quanto em co-NP, eu não coloco minhas fichas nele ser NP-completo...)
P vs NP é uma questão fundamental e central em ciência da computação. Como diria o pessoal da Mastercard, uma prova de P vs NP não tem preço.
Esse o papo de se os algoritmos polinomiais realmente são rápidos só importa se você está fazendo afirmações sensacionalistas como essas de criptografia de banco*. O problema P vs NP é muito mais do que só isso, e dizer que uma prova pode ser limitada só porque o algoritmo pode ter que ser super lerdo é algo completamente míope.
*sem contar que fatorar inteiros nem é NP-completo, deviam pelo menos dar de exemplo um problema NP-completo de verdade, como o do cacheiro viajante :P
(Ok, ninguém provou se fatorar é NP-completo ou não ainda, mas como esse problema está tanto em NP quanto em co-NP, eu não coloco minhas fichas nele ser NP-completo...)
> P vs NP é uma questão fundamental e central em
> ciência da computação.
> Como diria o pessoal da Mastercard,
> uma prova de P vs NP não tem preço.
Legal!
> O problema P vs NP é muito mais do que só isso,
Realmente, a questão P=?NP trata de algo bem mais
fundamental que segurança de bancos. Mas mencionar
bancos é um bom gancho para despertar a atenção.
:-)
> e dizer que uma prova pode ser limitada
> só porque o algoritmo pode ter que ser super
> lerdo é algo completamente míope.
Humm. Acho que não entendi...
:-(
> ciência da computação.
> Como diria o pessoal da Mastercard,
> uma prova de P vs NP não tem preço.
Legal!
> O problema P vs NP é muito mais do que só isso,
Realmente, a questão P=?NP trata de algo bem mais
fundamental que segurança de bancos. Mas mencionar
bancos é um bom gancho para despertar a atenção.
:-)
> e dizer que uma prova pode ser limitada
> só porque o algoritmo pode ter que ser super
> lerdo é algo completamente míope.
Humm. Acho que não entendi...
:-(
A segurança de dados foi só um exemplo.
Até o pouco que consigo enxergar, a questão é bem mais interessante, daí a discussão.
Abraço a todos.
Até o pouco que consigo enxergar, a questão é bem mais interessante, daí a discussão.
Abraço a todos.