>>> Is it possible to invent a computer that computes anything in a flash?
Eu acho essa formulação completamente mistificante, pois existem muitos problemas em P absolutamente inviáveis, quer seja porque a constante que multiplica é muito alta, quer seja porque qualquer relação polinomial com expoente maior igual a 5 é absolutamente inviável para um número grande de dados. Esses problemas são chamados de galáticos, aliás. Estão em P, mas não têm solução eficiente. Ou seja, pode ser que P=NP e mesmo assim muitos problemas fiquem fora do que seja viável de ser implementado. Resumindo, é fortemente debatível a escolha da classe P como a classe dos problemas com solução eficiente. Em muitos domínios algoritmos quadráticos são descartados por serem demorados demais. []s Em sex., 1 de dez. de 2023 às 15:16, Joao Marcos <botoc...@gmail.com> escreveu: > https://youtu.be/pQsdygaYcE4?si=jHZ2ttBX-rJjGPpK > Is it possible to invent a computer that computes anything in a flash? > Or could some problems stump even the most powerful of computers? How > complex is too complex for computation? The question of how hard a > problem is to solve lies at the heart of an important field of > computer science called computational complexity. Computational > complexity theorists want to know which problems are practically > solvable using clever algorithms and which problems are truly > difficult, maybe even virtually impossible, for computers to crack. > This hardness is central to what’s called the P versus NP problem, one > of the most difficult and important questions in all of math and > science. > > https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/ > > > JM > > -- > LOGICA-L > Lista acadêmica brasileira dos profissionais e estudantes da área de > Lógica <logica-l@dimap.ufrn.br> > --- > Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" > dos Grupos do Google. > Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie > um e-mail para logica-l+unsubscr...@dimap.ufrn.br. > Para acessar esta discussão na web, acesse > https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAO6j_Lh0hA-6%2BaL3i3PWQZrw%2B113LDznomaPp7C_ZHx1s4NPNQ%40mail.gmail.com > . > -- Marcelo Finger Departament of Computer Science, IME-USP http://www.ime.usp.br/~mfinger ORCID: https://orcid.org/0000-0002-1391-1175 ResearcherID: A-4670-2009 Instituto de Matemática e Estatística, Universidade de São Paulo Rua do Matão, 1010 - CEP 05508-090 - São Paulo, SP -- LOGICA-L Lista acadêmica brasileira dos profissionais e estudantes da área de Lógica <logica-l@dimap.ufrn.br> --- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+unsubscr...@dimap.ufrn.br. Para acessar esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAGG7Aw2r1Jpe-%2Bf1PEOtEfkKxycrRvyWfW2t1DoMjyJBggsCWw%40mail.gmail.com.
