b'\n_START_ARTICLE_\nP-completo\n_START_SECTION_\nMotiva\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nA classe P, normalmente considerada como o conjunto de todos os problemas "trat\xc3\xa1veis" por um computador sequencial, cont\xc3\xa9m a classe NC, que consiste naqueles problemas que podem ser resolvidos eficientemente por um computador paralelo. Isto acontece porque computadores paralelos podem ser simulados em m\xc3\xa1quinas sequenciais._NEWLINE_N\xc3\xa3o se sabe se NC\xc2\xa0=\xc2\xa0P. Em outras palavras, ainda n\xc3\xa3o sabemos se existem problemas trat\xc3\xa1veis que s\xc3\xa3o inerentemente sequenciais. Assim como suspeita-se que P n\xc3\xa3o \xc3\xa9 igual a NP, tamb\xc3\xa9m suspeita-se que NC n\xc3\xa3o \xc3\xa9 igual a P._NEWLINE_Da mesma forma, a classe L cont\xc3\xa9m todos os problemas que podem ser resolvidos por um computador sequencial usando espa\xc3\xa7o logar\xc3\xadtmico. Tais m\xc3\xa1quinas rodam em tempo polinomial porque elas podem ter um n\xc3\xbamero polinomial de configura\xc3\xa7\xc3\xb5es. Suspeita-se que L\xc2\xa0\xe2\x89\xa0\xc2\xa0P; isto \xc3\xa9, que alguns problemas que podem ser resolvidos em tempo polinomial tamb\xc3\xa9m requerem mais do que espa\xc3\xa7o logar\xc3\xadtmico._NEWLINE_De modo similar ao uso dos problemas NP-completos para analisar a quest\xc3\xa3o P\xc2\xa0=\xc2\xa0NP, os problemas P-completos, vistos como os problemas "provavelmente n\xc3\xa3o paraleliz\xc3\xa1veis" ou "provavelmente inerentemente sequenciais", tamb\xc3\xa9m s\xc3\xa3o \xc3\xbateis de maneira semelhante ao estudo da quest\xc3\xa3o NC\xc2\xa0=\xc2\xa0P. Encontrar uma forma eficiente de paralelizar a solu\xc3\xa7\xc3\xa3o de algum problema P-completo \xc3\xa9 equivalente a provar que NC\xc2\xa0=\xc2\xa0P. Isto tamb\xc3\xa9m pode ser pensado como "problemas que requerem espa\xc3\xa7o super-logar\xc3\xadtmico"; uma solu\xc3\xa7\xc3\xa3o em espa\xc3\xa7o logar\xc3\xadtmico para um problema P-completo (usando a defini\xc3\xa7\xc3\xa3o baseada nas redu\xc3\xa7\xc3\xb5es em espa\xc3\xa7o logar\xc3\xadtmico) implicaria em L\xc2\xa0=\xc2\xa0P._NEWLINE_A l\xc3\xb3gica por tr\xc3\xa1s disso \xc3\xa9 an\xc3\xa1loga a l\xc3\xb3gica de que uma solu\xc3\xa7\xc3\xa3o em tempo polinomial para um problema NP-completo provaria que P\xc2\xa0=\xc2\xa0NP: se n\xc3\xb3s temos uma redu\xc3\xa7\xc3\xa3o NC a partir de algum problema em P para um problema A, e uma solu\xc3\xa7\xc3\xa3o NC para A, ent\xc3\xa3o NC\xc2\xa0=\xc2\xa0P. Da mesma forma, se n\xc3\xb3s temos uma redu\xc3\xa7\xc3\xa3o em espa\xc3\xa7o logar\xc3\xadtmico a partir de algum problema em P para um problema A, e uma solu\xc3\xa7\xc3\xa3o em espa\xc3\xa7o logar\xc3\xadtmico para A, ent\xc3\xa3o L\xc2\xa0=\xc2\xa0P.\n_START_SECTION_\nProblemas que n\xc3\xa3o se sabe se est\xc3\xa3o em P-completo\n_START_PARAGRAPH_\nN\xc3\xa3o se sabe se alguns problemas est\xc3\xa3o em NP-dif\xc3\xadcil, nem em P. Esses problemas (por exemplo, fatora\xc3\xa7\xc3\xa3o de inteiros) s\xc3\xa3o suspeitos de serem dif\xc3\xadceis. De modo similar, existem problemas que n\xc3\xa3o se sabe se est\xc3\xa3o em P-completo ou NC, mas acredita-se que s\xc3\xa3o dif\xc3\xadceis de paralelizar. Exemplos incluem formas do problema de decis\xc3\xa3o para encontrar o m\xc3\xa1ximo divisor comum de dois n\xc3\xbameros e determinar qual resposta o algoritmo de Euclides estendido retornaria ao receber dois n\xc3\xbameros.'