Completo (complexidade): diferenças entre revisões
m Marcado que carece de mais notas, usando FastButtons |
concordancia |
||
| Linha 1: | Linha 1: | ||
{{mais notas|data=julho de 2015}} |
{{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 |
Na [[Complexidade_computacional|teoria da complexidade computacional]], um [[Problema_computacional|problema computacional]] é '''completo''' para a [[Classe_de_complexidade|classe de complexidade]] se ele está, 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). |
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: | 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]]. |
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 |
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 têm uma solução computacional "fácil". |
||
Geralmente, as classes de complexidade que são recursivamente |
Geralmente, as classes de complexidade que são recursivamente enumeráveis possuem problemas completos, enquanto que as classes que não são recursivamente enumeráveis, não tê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 têm problemas completos, enquanto [[RP_(complexidade_computacional)|RP]], [[ZPP]], [[BPP]] e [https://en.wikipedia.org/wiki/TFNP TFNP] não tê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> |
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> |
||
Revisão das 12h23min de 17 de julho de 2015
 |
Na teoria da complexidade computacional, um problema computacional é completo para a classe de complexidade se ele está, 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 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).
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 têm uma solução computacional "fácil".
Geralmente, as classes de complexidade que são recursivamente enumeráveis possuem problemas completos, enquanto que as classes que não são recursivamente enumeráveis, não têm até o momento nenhum problema completo conhecido. Por exemplo, as classes NP, co-NP, PLS, PPA todas têm problemas completos, enquanto RP, ZPP, BPP e TFNP não tê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 BPPM (BPP com Máquina oráculo M) sem nenhum problema completo. [1]
References
- ↑ 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.