Re: [Logica-l] P vs. NP - The Greatest Unsolved Problem in Computer Science

2023-12-02 Por tôpico Walter Carnielli 
Exatamente,  Mr.Finger tem razão .
Dado um ponto x  numa função exponencial com valor y= e(x), existe um
polinomio p tal que p(x)> e(x)...

Sem contar os problemas quanticamente dificeis destinados a embasbacar os
computadores quanticos (a existir), para ajudar na criptografia quantica.

Abs
Walter




> 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 
> 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 
>> ---
>> 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/-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 
> ---
> 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
> 
> .
>

-- 
LOGICA-L
Lista acadêmica brasileira dos profissionais e estudantes da área de Lógica 

--- 
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/CAOrCsLcqO9Mg5gyC%3D2-4LnahnnTT6wG5dBCHK%3DZMw1hYxGSpjA%40mail.gmail.com.

Re: [Logica-l] P vs. NP - The Greatest Unsolved Problem in Computer Science

2023-12-01 Por tôpico Rafael Santos Coelho 
Caros colegas e ilustre professor Marcelo,

On Fri, Dec 1, 2023 at 1:19 PM Marcelo Finger  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 
> 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 
>> ---
>> 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/-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 
> ---
> 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/CAGG

Re: [Logica-l] P vs. NP - The Greatest Unsolved Problem in Computer Science

2023-12-01 Por tôpico Marcelo Finger 
>>> 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 
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 
> ---
> 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/-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 

--- 
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.

[Logica-l] P vs. NP - The Greatest Unsolved Problem in Computer Science

2023-12-01 Por tôpico Joao Marcos 
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 

--- 
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.