Tópico: Resolva um probleminha de matemática e ganhe U$1000000: P=NP?

[Eleitor de Mário Oliveira]

http://www.claymath.org/millennium/P_vs_NP/

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair from taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf

[Snake]

O site QEDen criou um Wiki para ajudar a resolver esse e os outros seis "problemas do milênio".

http://www.qeden.com/wiki/Main_Page

[Südenbauer]

A Guinevere contribui com esse wiki.

[Oliver]

Atualmente tenho me preocupado apenas em resolver problemas do tipo SUDOKU...

[Guinevere]

A Guinevere contribui com esse wiki.

É, eu estou lá com meu nome de macho, mas não acredito que vá dá certo. Entretanto, é uma oportunidade e tanto pra aprender.

Atualmente tenho me preocupado apenas em resolver problemas do tipo SUDOKU...

Que é NP-Completo... um dia você vai acabar se interessando por esse outro problema, cara!

[Andre]

Eu nunca consegui entender direito esse negócio de NP e P, alguém pode me explicar de uma maneira resumida, e de preferencia com exemplos de problemas de cada um dos dois tipo?

[Guinevere]

Voce le Inglês? eu fiz isso n vezes em ingles, uma delas no tal wiki: http://www.qeden.com/wiki/P_versus_NP:Math_Lite_Intro

Se não entender eu tenho de novo, em pt, ok?

[Andre]

Deixa eu ver se eu entendi, P seriam problemas mais diretos, como colocar numeros em ordem crescente, ver se o número é primo, etc e NP seriam problemas que exigem o uso da lógica, como o sudoku?

[Guinevere]

Não.

Os problemas em P também estão dentro de NP.

Os "difíceis" a gente ainda não sabe se estão dentro ou fora de P (se tem solucao "fácil)

Como assim "exigem o uso da lógica"? Todo problema computacional é de lógica...

[Oliver]

Atualmente tenho me preocupado apenas em resolver problemas do tipo SUDOKU...

Que é NP-Completo... um dia você vai acabar se interessando por esse outro problema, cara!

hummm...será?

[Guinevere]

Você chega lá... tô bolando aqui um tópico definitivo sobre o assunto que vai fazer todo mundo entender tudo de vez (e alguns se interessarem)

[Eleitor de Mário Oliveira]

Pelo que entendo, os problemas P teriam um algorítimo rápido (e existe uma definição objetivo de "rápido") para serem solucionados. Enquanto os NP são de tentativa e erro. Deve-se tentar todos os casos até atingir o desejado.

Por exemplo, uma equação do primeiro grau é um problema P. Todas tem a estrutura geral:
ax+b=c
O algorítimo de resolução delas é:
1º) Se b for diferente de 0, subtrair ambos lados da equação por b.
2º) Se a for diferente de 1 ou 0, dividir ambos lados da equação por a.

Assim, digamos que a=5 , b=3 e c=13. Temos:

5x+3=13
(5x+3)-3=13-3
5x=10
(5x)/5=10/5
x=2

Não foi preciso ir chutando o valor de x até chegar num resultado que batesse. O que seria impraticável, diga-se de passagem.

Um exemplo de problema NP seria aqueles desafios de raciocínio que aparecem em revistas, do tipo que você tem que dispor vizinhos numa seqüencia com base em informações parciais. Estes problemas, até onde sabemos, não tem um algorítimo que os solucione rapidamente. Apenas temos a tentativa e erro.

[Guinevere]

Dante, só um detalhe que todo mundo confunde:
P está também "dentro" de NP. Os problemas "difíceis" são os NP-completos, que não se sabe se estão fora de P ou não.




Vejam esse desenho.

[Andre]

Esse assunto me deixa muito confuso, embora eu adore matemática

Com 'exigir lógica' quis dizer usar algo que não esta explicitamente escrito, como o exemplo que o Dante deu

[Guinevere]

O que é estar " explicitamente escrito"?

[Andre]

Não ser necessário o uso de suposições.

[Guinevere]

Mas problemas NP nao exigem "suposições"...

Você está usando uns termos meio extranhos, mas calma que vou fazer o tal artigo.

[Guinevere]

Olhem isso, agora: ../forum/topic=5819.new#new