Algoritmos Probabilísticos, Parte 4: Classes de Complexidade

Diversos círculos representando diferentes classes de complexidade. O círculo representando a classe PP contém as classes BQP, que por sua vez contém a classe BPP. A classe BPp contém as classes RP, coRP, ZPP e P. A classe ZPP está na intersecção entre RP e coRP. A classe P está contida na classe ZPP.
A classe BQP será vista em outro momento. Fonte: Wikipedia.
Círculos representando diferentes classes de complexidade. Semelhante à imagem anterior, mas inclui a classe P, NP, co-NP e NP-Completo. A classe NP inclui as classes RP, ZPP e P. A classe co-NP inclui as classes co-RP, ZPP e P. A classe NP-Completo está contida em NP e não possui intersecções com outras classes aqui representadas.
Fonte

--

--

Computer Science professor at UFPel. Machine Learning and Artificial Intelligence practitioner and researcher.

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ricardo Araujo

Ricardo Araujo

Computer Science professor at UFPel. Machine Learning and Artificial Intelligence practitioner and researcher.