Enquete Encerrada (6)

Considerando votos válidos, pela primeira vez uma enquete termina empatada:

Você acha que P=NP?
2 Sim
2 Não
7 Não sabem ou não quiseram opinar

Claro que a maioria dos leitores não é familiarizada com lógica ou ciências da computação, e, mesmo para os familiarizados, não é um palpite fácil de se justificar. Eu votei em "Não" por acreditar que se "P=NP", já teriam encontrado um algoritmo polinomial para algum problema NP completo. Isso só se explica pelo meu otimismo quanto à capacidade racional do ser humano.

Para concluir, uma citação que ilustra a hipótese "P=NP" de maneira exagerada, mas acessível:

"If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss..."
-Scott Aaronson, MIT

Pensamento da hora:
"Não sou um Mozart, mas poderia ser um Gauss."

Abs do Vaps

Deus e o Bóson de Higgs

O Bóson de Higgs, segundo a wikipedia, "é uma partícula elementar escalar maciça hipotética predita para validar o modelo padrão atual de partícula". Em palavras mais acessíveis, os físicos usam hoje um modelo padrão para explicar o nosso mundo, que prevê a existência dessa partícula - mas ela nunca foi observada em laboratório.
E o que deus tem a ver com isso? Tudo a ver, pois o Bóson de Higgs também é chamado de partícula de deus. Ele leva esse apelido basicamente por um simples motivo: a comprovação de sua existência, validaria o modelo padrão, que traz grande explicação sobre como matéria e energia funcionam no nosso universo. Claro que não traria todas as repostas, como deus faria, mas seria um grande avanço científico.
A grande diferença entre a existência dessa partícula e a existência de deus, é que a primeira certamente é uma hipótese científica. Dawkins acredita que a existência de deus também o seja, mas discordo. Assim como deus, esse bóson foi "inventado" pelos homens para dar uma explicação ao mundo que experimentamos. Assim como essa partícula, deus é a resposta virtual a perguntas ainda não respondidas! O cerne da distinção está na possibilidade de verificação, através de um experimento, que a hipótese científica permite. Com o total funcionamento do LHC, o grande acelerador de partículas recém inaugurado, a comunidade científica do mundo aguarda ansiosa pela observação do Bóson de Higgs. E os físicos realmente apostam suas fichas nele!
Não consigo conceber um experimento que verificasse a existência de deus (coisa pro Vapstradamus!), mas, se verificada, explicaria muito mais do que uma partícula.
Por alguma coincidência "estranha", entre as pessoas que apostam alto no Bóson de Higgs, não há muitos apostadores em deus. Talvez devido a sua não possibilidade de verificação, a existência de deus seja mais uma muleta do que uma teoria científica, mas graças a "deus", temos grandes homens, sobre ombros de gigantes, buscando a verdade palpável.

Pensamento da hora:
"Se o Bóson de Higgs não existisse, seria preciso inventá-lo."

Abs do Vaps

Enquete NERD

Voltando com as enquetes, aproveito a minha empolgação acadêmica para publicar uma científica. Em ciências da computação, há um grande problema ainda não solucionado, envolvendo a relação entre as classes P e NP, se seriam iguais ou não. A wikipedia dá uma visão geral do problema para os mais curiosos. Fato é que, devido às implicações da resolução do problema e à dificuldade envolvida, a questão é um dos problemas do milhão do Clay Mathematics Institute.

Infelizmente, a enquete pode não nunca ter uma resposta correta conhecida, mas isso realmente não tem importância.

Pensamento da hora:
"A metáfora está para a regra de três, assim como a linguística está para a matemática"

Abs do Vaps

Exercício de Autômato

Conforme o prometido, inicio a sessão NERD, onde vou compartilhar com os leitores parte do dia-a-dia de um estudante de ciência de computação. Claro que pouca gente vai entender, mas este ainda é um blog sobre assuntos aleatórios; e, para os mais curiosos, basta procurar os conceitos não entendidos no pai dos burros.

Transcrevo um exercício que acredito ter resolvido, mas não tenho certeza, sobre autômatos finitos determinísticos (DFA):

Suponha que p e q são estados distinguíveis de um dado DFA A com n estados. Como função de n, qual é o menor limite superior para o tamanho que a menor string que distingue p de q pode ter?

Se p é um estado final de A e q não é, então a string ε de tamanho 0 distingue ambos.
Se q é um estado final de A e p não é, então a string ε de tamanho 0 distingue ambos.
Restam os casos onde p e q são ambos estados finais ou não finais. Sem perda de generalidade, suponho que p e q não sejam estados finais.
Chamemos de w a menor string que distingue p de q. Provarei que o tamanho de w é menor ou igual a (n-1)(n-2)/2, ou:
|w|<=(n-1)(n-2)/2
Seja k o número de estados não-finais de A, 1 < k < n, pois deve haver pelo menos 1 estado final para que p e q possam ser distiguíveis, e já consideramos p e q como não-finais.
Sem perda de generalidade, suponho que w leva p a um estado final, e leva q a um estado não-final, o que distingue ambos.
Seja P={P0,P1...Pj} a sequência dos estados que formam o caminho que leva p a tal estado final, recebendo w. P0=p e Pj é um estado final, sendo j=w e P tem j+1 elementos, ou |P| =j+1
Analogamente, definimos Q={Q0,Q1...Qj}, com Q0=q, e Qj é um estado não final.
Seja PQ a sequência dos pares {Px,Qx}, para todo 0<=x<=j.
PQ={{P0,Q0},{P1,Q1}...{Pj,Qj}}, |PQ|=j+1
Seja G={G1,G2...Gk} o conjunto de estados não finais de A, com k elementos.
Seja F={F1, F2...F(n-k)} o conjunto de estados finais de A, com n-k elementos.
Seja G' o conjunto de pares de estados não finais, ou o conjunto de todos os subconjuntos de G que tenham exatamente 2 elementos. Sabemos que G' contém exatamente k(k-1)/2 elementos se k>=2, que é a combinação de k elementos, tomados 2 a 2; ou |G'|=0, se k<2.
Analogamente, definimos F' como o conjunto dos pares de estados finais, tendo (n-k)(n-k-1)/2 elementos se n-k>=2; ou |F'|=0 elementos ,se n-k<2
Sabemos que todos os pares {Px,Qx}, para todo x < j, pertencem a exatamente um dos conjuntos F' ou G'. Caso contrário, se houvesse um y < j para qual o par {Py,Qy} não pertencesse nem a F' nem a G', ou seja, só um dos estados Py e Qy é final, encontraríamos um caminho possível P'={P0,P1...Py}, correspondente a uma string z (substring de w) que distinguisse os estados p e q, e teríamos
z=y < j=w, e w não seria a menor string a distuinguir p e q.
Provaremos por aburdo que a sequência PQ não tem pares repetidos:
Supomos que há dois pares, tais que {Px,Qx}={Py,Qy}, com x < y. Logo, há um loop em w que pode ser retirado do caminho e há um caminho possível P'={P0,P1...Px,P(y+1)....Pj}, correspondente a uma string z, que leva p a Pj e q a Qj, tal que |z|=|w|-(y-x) < |w|, e w não seria a menor string a distinguir p e q.
Assim, podemos chamar PQ de um conjunto sem elementos repetidos. Subtraímos o conjunto formado pelo par {{Pj,Qj}} do conjunto PQ, para formarmos o conjunto PQ', com j elementos.
Como cada elemento de PQ' pertence só a um dos conjuntos F' e G', formamos uma partição de PQ', formada pelos conjuntos PQF e PQG onde PQF é a intersecção de PQ' e F'. Analogamente, PQG é a intersecção de PQ' e G'.
O número de elementos de PQ' é a soma do número de elementos dos suconjuntos que o particionam, ou:
|PQ'|=|PQF|+|PQG|
Propriedade da intersecção:
|PQF|<=|F'|
|PQG|<=|G'|
Logo, |PQ'|<=|F'|+|G'|=
(k)(k-1)/2+(n-k)(n-k-1)/2, se 1 < k < n-1
ou (n-1)(n-2)/2, se k=n-1
Sabemos, pela combinatória, que |F'|+|G'| é máximo quando k=n-1.
Finalmente, temos:
|PQ'|= j = w <=(n-1)(n-2)/2 c.q.d.

De fato, pra mim não está provado que este é o menor limite superior, mas deixo isso pra depois.

Críticas são bem-vindas!

Pensamento da hora:
"Cansei, mas foi melhor que ver o BBB!"

Abs do Vaps