Hoje estava a fazer uma lista (interminável) dos exercícios que nos últimos dias deixei em aberto por falta de ideias. Ao olhar para um desses exercícios dei comigo a pensar: "Mas este problema tem muito pouca coisa em jogo, portanto deve ter uma resolução simples". Num piscar de olhos, esqueci-me do problema e mergulhei um pouco na teoria da complexidade! Veio-me à mente uma questão... Seja C o conjunto de todos os problemas cujos dados são poucos e fáceis de entender. Dito de outro modo, C é o conjunto de todos os problemas cujo enunciado é facilmente entendido. Seja C_0 o conjunto de todos os problemas que pertencem a C e cuja resolução é fácil. Julgo que C_0 está propriamente contido em C. Por exemplo, o último Teorema de Fermat pode ser visto como um problema de enunciado aparentemente simples mas cuja resolução é assim um bocadinho para o complicado (eufemismo)! Mas a questão que me assaltou a mente foi a seguinte: será que C_0 é denso em C? Ou, por outras palavras, será que pegando no saco de todos os problemas matemáticos que pertencem a C e tirando um ao acaso a probabilidade desse problema pertencer a C_0 é igual a 1? Depois, já no comboio a caminho de casa, recordei-me de algumas coisas que aprendi nas aulas de Complexidade e Criptografia e lembrei-me que esta questão pode estar relacionada com as classes P e NP. Infelizmente, os meus conhecimentos de complexidade não são suficientes para aprofundar mais este assunto, mas um dia gostava de o fazer!
São estas as coisas em que um matemático se arrisca a pensar quando cái na distracção!
P.S. Este post é dedicado à Andrea, ao Bob e à Catherine (ah saudade!)
4 comentários:
... estou mais viva do que tu julgas! Passo mts vezes por aqui pq divirto-me imenso a ler os teus post. Com este, em particular, rebolei a rir, pois fez-me lembrar mts dos delírios q eu tb tenho.
Beijocas
PS: Lá passei a Politopos.. ufff :)
Pensa no conjunto de todos os números inteiros que não se conseguem descrever com menos de 100 palavras.
Agora pensa no menor deles...
Depois no maior.
Bolas... afinal, qualquer um destes elementos pertence ou não pertence ao conjunto? É que qualquer um deles acabou de ser descrito em menos de 100 palavras!
Parabéns por passares a Politopos! E boa sorte, caso ainda te falte algum! Ainda bem que gostas dos meus posts, só mostra que tens bom gosto! eheh =P beijinhos
Dark, aí a falácia é claramente a ambiguidade da palavra "descrever" . Além do mais estás a admitir que o tal conjunto admite máximo e mínimo o que depende da relação de ordem que estás a considerar. Por exemplo, se calhar se for a relação induzida por aquela da tua ex-colega, em que "i<2", o conjunto deixa de ter máximo e mínimo!!
Enviar um comentário