Complexidade computacional: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m correção de texto extra em parâmetro página e edição |
Resgatando 2 fontes e marcando 0 como inativas. #IABot (v2.0beta14) |
||
Linha 186:
A classe de complexidade P é muitas vezes vista como uma abstração matemática de modelagem dessas tarefas computacionais que admitem um algoritmo eficiente. Esta hipótese é chamada de tese de Cobham-Edmonds. A classe de complexidade NP, por outro lado, contém muitos problemas que as pessoas gostariam de resolver de forma eficiente, mas para os quais nenhum algoritmo eficiente é conhecido, como o [[Problema de satisfatibilidade booleana|problema da satisfatibilidade booleana]], o [[problema do caminho hamiltoniano]] e o [[Cobertura de vértices (teoria dos grafos)|problema da cobertura de vértices]]. Como as máquinas de Turing determinística são máquinas de Turing não-determinísticas especiais, é fácil observar que cada problema em P também é membro da classe NP.
A questão de saber se P é igual a NP é uma das questões mais importantes em aberto na ciência da computação teórica por causa da gama de implicações de uma solução.<ref name="Sipser2006">Veja {{harvnb|Sipser|2006|loc= Chapter 7: Time complexity}}</ref> Se a resposta for sim, para muitos problemas importantes pode ser mostrado que há soluções mais eficientes para eles. Estes incluem vários tipos de problemas de [[programação inteira]] em [[investigação operacional]], muitos problemas na área de [[logística]], [[previsão da estrutura de proteínas]] na biologia,<ref>{{Citation|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|last=Berger|first=Bonnie A.|journal=Journal of Computational Biology|year=1998|volume=5|number=1|pages=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|last2=Leighton|first2=T|issue=1|postscript=. }}</ref> e capacidade de encontrar provas formais de teoremas da [[matemática pura]].<ref>{{Citation|last=Cook|first=Stephen|authorlink=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]]|year=2000|month=April|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18|postscript=.|archiveurl=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf}}</ref> O problema P versus NP é um dos [[Problemas do Prémio Millenium|Problemas do Prêmio Millenium]] (Millenium Prize Problems) proposto pelo [[Clay Mathematics Institute|Instituto Clay de Matemática]] (Clay Mathematics Institute). Existe um prêmio de um milhão de dólares para resolver o problema.<ref>{{Citation|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|authorlink=Arthur Jaffe|year=2006|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18|postscript=.}}</ref>
===Problemas em NP que não se sabe se pertencem a P ou a NP-completo===
Linha 333:
==Ligações externas==
* [https://web.archive.org/web/20100726082118/http://qwiki.stanford.edu/wiki/Complexity_Zoo The Complexity Zoo]
[[Categoria:Complexidade]]
| |||