P vs. NP - The Greatest Unsolved Problem in Computer Science

[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

[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

--
LOGICA-L
Lista acadêmica brasileira dos profissionais e estudantes da área de Lógica <logi...@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+u...@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

[Rafael Santos Coelho]

Caros colegas e ilustre professor Marcelo,

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

 

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+u...@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.

[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 

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+u...@dimap.ufrn.br.