Religião é Veneno. Fórum de discussão de assuntos relevantes para o ateísmo, agnosticismo, humanismo e ceticismo. Defesa da razão e do Método Científico.
Fórum de discussão de assuntos relevantes para o ateísmo, agnosticismo, humanismo e ceticismo. Defesa da razão e do Método Científico. Combate ao fanatismo e ao fundamentalismo religioso.
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.
Entre os brasileiros envolvidos no problema estão Francisco Antônio Doria e Newton da Costa ( conhecido por suas formulações da lógica para-consistente ). O abstract do artigo mais citado da equipe está disponível aqui.
Houve um artigo sobre ambos em uma Sciam de Fevereiro ou Março, se não me falha a memória.
Alguém já conseguiu algum dia resolver de maneira inteligente qualquer um dos problemas NP-completos existentes? Pelo que eu sei, até o clássico do caixeiro viajante continua em aberto.
The world's mine oyster, which I with sword will open. - William Shakespeare Grande parte das pessoas pensam que elas estão pensando quando estão meramente reorganizando seus preconceitos. - William James Agora já aprendemos, estamos mais calejados... os companheiros petistas certamente não vão fazer as burrices que fizeram neste primeiro mandato. - Luis Inácio, 20/10/2006
Azathoth escreveu:Entre os brasileiros envolvidos no problema estão Francisco Antônio Doria e Newton da Costa ( conhecido por suas formulações da lógica para-consistente ). O abstract do artigo mais citado da equipe está disponível aqui.
Houve um artigo sobre ambos em uma Sciam de Fevereiro ou Março, se não me falha a memória.
Você é parente do Francisco Antônio Doria?
"Let 'em all go to hell, except cave 76" ~ Cave 76's national anthem
user f.k.a. Cabeção escreveu:Você é parente do Francisco Antônio Doria?
Sim.
Legal, já conversou sobre esse problema com ele?
Os matemáticos em geral não gostam de soluções que usem o axioma da escolha. Quando se vale desse axioma para provar alguma proposição, deve-se provar que essa proposição implica também naquele axioma, o que significa que ambas são equivalentes. Só aí, eu acho que seu parente ficaria milionário.
ps: é óbvio que eu sei que ele já sabe disso, só quis fazer um comentário.
"Let 'em all go to hell, except cave 76" ~ Cave 76's national anthem
Azathoth escreveu:Entre os brasileiros envolvidos no problema estão Francisco Antônio Doria e Newton da Costa ( conhecido por suas formulações da lógica para-consistente ). O abstract do artigo mais citado da equipe está disponível aqui.
Houve um artigo sobre ambos em uma Sciam de Fevereiro ou Março, se não me falha a memória.
Sim. O da Costa está fazendo uso da teoria de conjuntos CFZ na resolução deste problema. Ele já mostrou que não dá pra provar pela CFZ que P=NP. Resta verificar se é indecidível ou se dá pra provar a negação de P=NP.
Visite minha página http://filomatia.net. Tratando de lógica, filosofia, matemática etc.
