Matemática discreta ramo da matemática onde se estudam estruturas matemáticas ( conjuntos , etc .) em que os seus elementos podem ser enumerados utilizando números inteiros (“ elemento n º 1 , elemento n º 2 , etc .), como por exemplo o conjunto dos números naturais { 0,1,2 , …} ou os grafos .
Equação diferencial igualdade que relaciona uma função com as suas derivadas .
PSPACE classe de problemas cuja solução pode ser obtida utilizando uma quantidade de memória razoável ( num computador ). vez ). A classe P está contida em NP e julga-se que P ≠ NP , mas o problema de saber se P = NP está em aberto sendo um dos 7 problemas do Milénio estabelecidos pelo Instituto Clay de Matemática , que oferece um prémio de 1 milhão de dólares pela resolução deste problema .
Resultados e discussão
Existem vários resultados que mostram que as técnicas atualmente existentes parecem não ser suficientemente poderosas para resolver a questão “ P = NP ?”, sendo aparentemente necessário novas técnicas . As técnicas utilizadas para resolver este tipo de questões são tipicamente baseadas em noções de matemática discreta . Na matemática discreta estudam-se estruturas matemáticas ( conjuntos , etc .) em que os seus elementos podem ser enumerados utilizando números inteiros (“ elemento n º 1 , elemento n º 2 , etc .), como por exemplo o conjunto dos números naturais { 0,1,2 , …}, ao contrário do que acontece na matemática contínua , onde tipicamente se estudam estruturas envolvendo números reais , cujos elementos não podem ser enumerados através de números inteiros . No entanto , a matemática contínua teve grandes desenvolvimentos ao longo dos últimos séculos , sendo natural perguntar se poderá trazer algum tipo de contributo para esclarecer estas questões . Mas para isso ser possível , é primeiro necessário caracterizar de forma contínua as classes de complexidade envolvidas nestes problemas , como as classes P , NP , ou outras classes tais como PSPACE ( problemas que se podem resolver sem se utilizar demasiada “ memória ” num computador ), entre outras .
Um problema que é necessário ultrapassar e que origina diversas dificuldades é que existe uma noção de tempo que é “ robusta ” ( invariante ) sobre estruturas discretas e que nos permite definir classes como P ou NP . Se efetuarmos uma tarefa “ passo-a-passo ”, podemos efetuar cada passo mais depressa ou mais devagar , mas o número total de passos ( o “ tempo ” utilizado para definir P e NP formalmente ) não se altera . Mas em matemática contínua ( em que se trabalha sobre os números reais ) ao fazer operações como “ acelerar ” ou “ retardar ” a evolução de um sistema ( pode-se pensar numa partícula que se move ), está-se a alterar a noção de tempo “ usual ”, o que faz com que esta não seja apropriada por não ser “ robusta ” ( invariante ) face a este tipo de operações , ao contrário do que acontece no caso discreto .
Utilizando diversos resultados da teoria de equações diferenciais , da análise , e da teoria da computação , mostramos que é possível definir uma noção de tempo invariante sobre estruturas contínuas que não corresponde ao tempo “ usual ”, mas sim ao comprimento da curva de uma trajetória de um sistema que modela um processo computacional ( utilizando a analogia de uma partícula que se move , o comprimento da curva é a distância total já percorrida pela partícula , e que não depende da velocidade com que a partícula se move – ver Fig . 2 ). Com esta ideia e utilizando técnicas apropriadas , conseguimos mostrar que é possível caracterizar classes de complexidade tais como P , PSPACE , e outras classes de definição mais complexa , tais como a hierarquia de Grzegorczyk e a classe das funções
32