Volume 5 Número 1 Julho 2023
Caracterização contínua de classes de complexidade computacional
Autores Daniel Graça 1 , 2
Afiliações
1
Departamento de Matemática , Faculdade de Ciências e Tecnologia , Universidade do Algarve 2 Instituto de Telecomunicações & Centro de Estudos e Desenvolvimento da Matemática no Ensino Superior , Universidade do Algarve
Revisão Escola : Agrupamento de escolas Dra Laura Ayres , Quarteira Alunos : Adriano Muncaciu , Bárbara Reis , Maria Vieira , Raquel Cavaco , Alexandra Durão , Margarida Brito , Eva Sousa , Jesse Velosa , Alexandre Magno , Francisco Rodrigues , Augusto Moreira , Carolina Silva e Jazmin Suarez
Sumário — Existem várias questões matemáticas em aberto envolvendo classes de problemas , conhecidas como classes de complexidade , que são oriundas da teoria da computação . A mais famosa destas questões é o problema “ P = NP ?”, que é um dos 7 problemas do Milénio estabelecidos pelo Instituto Clay de Matemática . As definições de classes como P e NP são efetuadas utilizando matemática discreta , que trabalha sobre estruturas discretas tais como o conjunto dos números naturais . No entanto , existe um corpo muito vasto de conhecimento em matemática contínua , que trabalha sobre estruturas contínuas como o conjunto dos números reais , sendo interessante perceber se é possível caracterizar classes de complexidade clássicas utilizando unicamente matemática contínua . Mostramos neste artigo que tal tarefa é exequível , embora ainda com algumas limitações . Abstract — There are several open mathematical questions involving classes of problems , known as complexity classes , which originate from the theory of computation . The most famous of these questions is the “ P = NP ?” problem , which is one of the 7 Millennium problems set by the Clay Mathematics Institute . The definitions of classes such as P and NP are made using discrete mathematics , which works on discrete structures such as the set of natural numbers . However , there is a vast body of knowledge in continuous mathematics , which works on continuous structures such as the set of real numbers , and it is interesting to see if it is possible to characterize classical complexity classes using only continuous mathematics . We show in this article that such a task is feasible , although with some limitations .
30