{"id":205,"date":"2008-09-05T10:48:03","date_gmt":"2008-09-05T13:48:03","guid":{"rendered":"http:\/\/scienceblogs.com.br\/cretinas\/2008\/09\/complexidade\/"},"modified":"2008-09-05T10:48:03","modified_gmt":"2008-09-05T13:48:03","slug":"complexidade","status":"publish","type":"post","link":"https:\/\/www.blogs.unicamp.br\/cretinas\/2008\/09\/05\/complexidade\/","title":{"rendered":"Complexidade"},"content":{"rendered":"

Minha postagem de ontem terminou com uma afirma\u00e7\u00e3o sobre o fato de haver programas de computador de diferentes graus de complexidade — isso era uma isca para algu\u00e9m me perguntar como se mede complexidade. Mas j\u00e1 que ningu\u00e9m mordeu o anzol, mordo-o eu mesmo! \ud83d\ude42
\nEm seu livro sobre computa\u00e7\u00e3o qu\u00e2ntica (assunto j\u00e1 muito bem tratado no Universo F\u00edsico<\/a>), Programming the Universe<\/em>, Seth Lloyd pondera que medidas de complexidade geralmente tentam capturar o ponto de equil\u00edbrio entre duas caracter\u00edsticas de um sistema: o quanto \u00e9 dif\u00edcil descrev\u00ea-lo ou o quanto \u00e9 dif\u00edcil constru\u00ed-lo.\u00a0
\nEle passa pelos conceitos de complexidade termodin\u00e2mica<\/em> (quantos bits s\u00e3o necess\u00e1rios para descrever precisamente um sistema) e complexidade algor\u00edtmica<\/em> (qual o comprimento do menor programa de computador capaz de gerar uma descri\u00e7\u00e3o do sistema), mas nota que essas formula\u00e7\u00f5es medem informa\u00e7\u00e3o bruta, n\u00e3o esfor\u00e7o ou estrutura.
\nLLoyd considera mais \u00fatil o conceito de complexidade computacional<\/em>\u00a0— o n\u00famero de opera\u00e7\u00f5es l\u00f3gicas (AND, NOT, OR, COPY) envolvidas na gera\u00e7\u00e3o de um resultado — e, mais \u00fatil ainda, o de profundidade l\u00f3gica<\/em>, ou o n\u00famero de opera\u00e7\u00f5es l\u00f3gicas do menor programa capaz de gerar esse mesmo resultado.
\nMas o conceito favorito \u00e9 o que ele chama de complexidade<\/span><\/em>\u00a0profundidade termodin\u00e2mica<\/em>, ou negentropia<\/em>\u00a0: o n\u00famero de bits relevantes<\/em> para a constru\u00e7\u00e3o de um sistema. “Relevantes”, no caso, s\u00e3o os bits que, se alterados, fariam do sistema uma outra coisa. Por exemplo, a posi\u00e7\u00e3o exata de cada \u00e1tomo de carbono em meu corpo n\u00e3o \u00e9 relevante pra eu ser o que (e quem) sou, mas o padr\u00e3o geral em que eles est\u00e3o organizados e a posi\u00e7\u00e3o das bases do DNA no n\u00facleo de minhas c\u00e9lulas s\u00e3o, claro, fundamentais.
\nOu: a posi\u00e7\u00e3o exata de cada mol\u00e9cula de oxig\u00eanio nesta sala n\u00e3o \u00e9 importante, mas a press\u00e3o, a composi\u00e7\u00e3o e a temperatura do ar, s\u00e3o.\u00a0
\nAssim: um sistema que requer muita informa\u00e7\u00e3o para ser reconhecido como aquilo que \u00e9 (um ser humano, um elefante, um nave espacial) tem alta profundidade\u00a0termodin\u00e2mica; j\u00e1 um sistema que, embora tenha muita informa\u00e7\u00e3o (as mol\u00e9culas de ar nesta sala, cada uma com sua composi\u00e7\u00e3o qu\u00edmica, posi\u00e7\u00e3o e velocidade), poderia continuar sendo exatamente o que \u00e9 (uma massa de ar preenchendo a sala), mesmo se boa parte dessa informa\u00e7\u00e3o mudasse, \u00e9 termodinamicamente “raso”.
\nIsso gera algumas quest\u00f5es interessantes sobre o grau de subjetividade –e de recursividade: em que n\u00edvel o sistema est\u00e1 sendo analisado — que fica impl\u00edcito no conceito de complexidade, mas essa \u00e9 uma discuss\u00e3o ara outra hora…<\/p>\n","protected":false},"excerpt":{"rendered":"

Minha postagem de ontem terminou com uma afirma\u00e7\u00e3o sobre o fato de haver programas de computador de diferentes graus de complexidade — isso era uma isca para algu\u00e9m me perguntar como se mede complexidade. Mas j\u00e1 que ningu\u00e9m mordeu o anzol, mordo-o eu mesmo! \ud83d\ude42 Em seu livro sobre computa\u00e7\u00e3o qu\u00e2ntica (assunto j\u00e1 muito bem […]<\/p>\n","protected":false},"author":545,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"pgc_sgb_lightbox_settings":"","_vp_format_video_url":"","_vp_image_focal_point":[],"footnotes":""},"categories":[3],"tags":[],"class_list":["post-205","post","type-post","status-publish","format-standard","hentry","category-geral"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/posts\/205","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/users\/545"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/comments?post=205"}],"version-history":[{"count":0,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/posts\/205\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/media?parent=205"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/categories?post=205"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blogs.unicamp.br\/cretinas\/wp-json\/wp\/v2\/tags?post=205"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}