Caros colegas e ilustre professor Marcelo, On Fri, Dec 1, 2023 at 1:19 PM Marcelo Finger <mfin...@ime.usp.br> wrote:
> >>> 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. > No geral, levando ao pé da letra, eu concordo com o seu ponto, mas só fazendo um adendo: a maneira como a gente "pragmaticamente" conceitua "rapidez algorítmica" parte de alguns pressupostos, como: 1) Que a palavra "algoritmo", em linhas gerais, significa *um procedimento bem descrito executado sequencialmente, que sempre termina* e *que está sempre correto* e 2) Que a palavra "rapidez" significa *eficiente do ponto de vista **clássico** de complexidade assintótica no pior caso, *que, como a gente sabe, é um ponto de vista essencialmente "pessimista" e "generalista" (ou seja, que coloca no mesmo "balaio" classes de instâncias "patológicas pouco expressivas" e classes de instâncias "extensas e mais usuais" que "capturam melhor" instâncias que "ocorrem no mundo real"). Existem visões alternativas (bem estudadas, mas não muito "mainstream") dentro da Teoria da Computação que relaxam/"violam" um ou ambos desses pressupostos. Por exemplo, existem modelos formais de computação que são paralelos, distribuídos e/ou probabilísticos (que relaxam/"violam" o pressuposto 1). Existem também, por exemplo, noções "heterodoxas" de eficiência computacional (que relaxam/"violam" o pressuposto 2) como eficiência do ponto de vista clássico de complexidade assintótica *no caso médio*, eficiência do ponto de vista clássico *de complexidade assintótica suavizada* e eficiência do ponto de vista não clássico *parametrizado**.* Inclusive, existe um programa de pesquisa relativamente recente e bem ativo na área de complexidade computacional parametrizada **especificamente voltado para problemas em P**. Resumindo: é possível, sim, um problema pertencer a P e só admitir algoritmos "pragmaticamente inviáveis" do ponto de vista clássico, mas ainda assim também admitir algoritmos "rápidos e não convencionais". Abraços aos colegas, Rafael Coelho > 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ê recebeu essa mensagem porque está inscrito 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 essa discussão na Web, acesse > https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAGG7Aw2r1Jpe-%2Bf1PEOtEfkKxycrRvyWfW2t1DoMjyJBggsCWw%40mail.gmail.com > <https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAGG7Aw2r1Jpe-%2Bf1PEOtEfkKxycrRvyWfW2t1DoMjyJBggsCWw%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- 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/CAOQK1JiOnUErDBObPMY2FirkS%2BdMQ-d510dYoPNmAQ3qRoy4Tw%40mail.gmail.com.
