Wikipédia

Completo (complexidade): diferenças entre revisões

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
m Marcado que carece de mais notas, usando FastButtons
concordancia
Linha 1:
{{mais notas|data=julho de 2015}}
Na [[Complexidade_computacional|teoria da complexidade computacional]], um [[Problema_computacional|problema computacional]] é '''completo''' para a [[Classe_de_complexidade|classe de complexidade]] se ele temestá, tecnicamente falando, entre os "mais difíceis" (e os "mais expressivos") problemas da classe de complexidade.
 
Mais formalmente, um problema ''p'' é chamado de '''difícil''' para a classe de complexidade ''C'' diante de um tipo dado de [https://pt.wikipedia.org/wiki/Redu%C3%A7%C3%A3o_(complexidade) redução], se existir tal redução de um problema em ''C'' para ''p''. Se o problema é ''díficil'' para a classe e ele também é um membro da classe, então ele é ''completo'' para esta classe (através deste tipo de redução).
Linha 6:
Um problema que é completo para a classe ''C'' é chamado de ''C-completo'', e a classe de todos os problemas completos para ''C'' é denotado ''C-completo''. A primeira classe completa que foi definida e também a mais conhecida é a classe [[NP-completo]], que contém vários problemas difíceis para resolver na prática. De maneira similar, um problema difícil para a classe ''C'' é chamado de ''C-hard'', ex: [[NP-hard]].
 
Normalmente se assume que a redução em questão não tem uma complexidade computacional mais alta que a própria classe. Portanto pode ser dito que se um problema ''C-completo'' tem uma solução "computacional fácil", então todos os problemas "''C''" também temtêm uma solução computacional "fácil".
 
Geralmente, as classes de complexidade que são recursivamente enumerávelenumeráveis possuem problemas completos, enquanto que as classes que não são recursivamente enumerávelenumeráveis, não temtêm até o momento nenhum problema completo conhecido. Por exemplo, as classes [[NP_(complexidade)|NP]], [[Co-NP|co-NP]], [https://en.wikipedia.org/wiki/PLS_(complexity) PLS], [https://en.wikipedia.org/wiki/PPA_(complexity) PPA] todas temtêm problemas completos, enquanto [[RP_(complexidade_computacional)|RP]], [[ZPP]], [[BPP]] e [https://en.wikipedia.org/wiki/TFNP TFNP] não temtêm nenhum problema completo conhecido (embora algum problema completo pode ser descoberto no futuro).
 
Existem classes sem problemas completos. Por exemplo, Sipser mostrou que existe uma linguagem '''M''' na qual '''BPP'''<sup>'''M'''</sup> ('''BPP''' com [https://pt.wikipedia.org/wiki/M%C3%A1quina_or%C3%A1culo Máquina oráculo] '''M''') sem nenhum problema completo. <ref>M. Sipser. On relativization and the existence of complete sets, Proceedings of ICALP'82, Springer-Verlag Lecture Notes in Computer Science volume 140, pp. 523-531, 1982.</ref>
Obtida de "https://pt.wikipedia.org/wiki/Completo_(complexidade)"