{"id":4131,"date":"2015-12-09T15:06:52","date_gmt":"2015-12-09T13:06:52","guid":{"rendered":"http:\/\/bilimvegelecek.com.tr\/?p=4131"},"modified":"2015-12-09T15:06:52","modified_gmt":"2015-12-09T13:06:52","slug":"kompleksite-teorisinde-zirveye-ulasildi-mi","status":"publish","type":"post","link":"https:\/\/bilimvegelecek.com.tr\/index.php\/2015\/12\/09\/kompleksite-teorisinde-zirveye-ulasildi-mi","title":{"rendered":"Kompleksite teorisinde yeni bir d\u00f6n\u00fcm noktas\u0131 m\u0131?"},"content":{"rendered":"

\u00a0<\/strong>G\u00f6rsel a\u00e7\u0131klamas\u0131:<\/strong> Yeni geli\u015ftirilen matematiksel algoritma izomorfik graf problemine meydan okuyor ve iki farkl\u0131 a\u011f\u0131n (network) kar\u015f\u0131la\u015ft\u0131r\u0131l\u0131p, bu iki a\u011f\u0131n asl\u0131nda ayn\u0131 olup olmad\u0131\u011f\u0131n\u0131n, daha \u00f6nce kullan\u0131lan algoritmalardan \u00e7ok daha az basamakta belirlenmesini sa\u011fl\u0131yor. Uyarlama Booya Bazooka.<\/p>\n

 <\/p>\n

Kompleksite teorisinde senelerden sonra en b\u00fcy\u00fck ilerleme s\u00f6ylentisi g\u00fcnlerdir internet ortam\u0131n\u0131 ayd\u0131nlat\u0131yor. L\u00e1szl\u00f3 Babai, \u015eikago \u00dcniversitesi\u2019nde matematik\u00e7i ve bilgisayar bilimci, geli\u015ftirdi\u011fi matematiksel algoritma ile iki farkl\u0131 a\u011f\u0131 (network) kar\u015f\u0131la\u015ft\u0131r\u0131p (a\u011flar\u0131n ne kadar b\u00fcy\u00fck ve kar\u0131\u015f\u0131k oldu\u011fu \u00f6nemli de\u011fil), bu iki a\u011f\u0131n (network) asl\u0131nda ayn\u0131 olup olmad\u0131\u011f\u0131n\u0131, daha \u00f6nce kullan\u0131lan algoritmalardan \u00e7ok daha az basamakta belirtiyor. Bilgisayar bilimcilerin \u00e7\u00f6z\u00fclmesi zor olarak g\u00f6rd\u00fckleri problemlerden birine a\u00e7\u0131klama gelmesi, onlar\u0131 olduk\u00e7a heyecanland\u0131rd\u0131.<\/p>\n

MIT bilgisayar bilimcisi Scott Aaronson, bu sonucun do\u011fru olmas\u0131 durumunda, teorik bilgisayar biliminin on y\u0131l\u0131n\u0131n bir sonucu olabilece\u011fini belirtti.<\/p>\n

Karma\u015f\u0131kl\u0131k teorisi, temelde, bilgisayar ile neyin kolay, neyin zor \u00e7\u00f6z\u00fclebilece\u011finin incelenmesidir. Ara\u015ft\u0131rmadaki \u00f6nemli nokta; problemi \u00e7\u00f6zmek i\u00e7in gerekli olan ad\u0131mlar\u0131n, girdilerin (inputs) boyutu ile beraber nas\u0131l b\u00fcy\u00fcd\u00fc\u011f\u00fcd\u00fcr. \u00d6rne\u011fin 983 veya 105227 say\u0131lar\u0131n\u0131n asal olup olmad\u0131\u011f\u0131 belirlemek istiyoruz. Bu hesaplamadaki bilgisay\u0131msal (komp\u00fctasyonel) ad\u0131mlar, say\u0131n\u0131n i\u00e7indeki rakamlar\u0131n say\u0131s\u0131na g\u00f6re yava\u015f\u00e7a b\u00fcy\u00fcr. Genellikle, bilgisay\u0131msal ad\u0131mlar rakamlar\u0131n say\u0131s\u0131na \u201cn\u201d dersek, \u201cn\u201d ile \u00fcsl\u00fc fonksiyon olu\u015fturacak \u015fekilde b\u00fcy\u00fcr; yakla\u015f\u0131k olarak n2 <\/sup>diyebiliriz. Bu tarz ifadeler polinom olarak ifade edilir ve problemin polinom zamanda \u00e7\u00f6z\u00fclebildi\u011fi belirtilir ve bu problemin karma\u015f\u0131kl\u0131k s\u0131n\u0131f\u0131 \u201cP\u201dye aittir.<\/p>\n

Di\u011fer bir yandan ise, 21, 122, 331 say\u0131lar\u0131n\u0131 t\u00fcm \u00e7arpanlar\u0131na (fakt\u00f6rlerine) b\u00f6lmek istedi\u011fimizi d\u00fc\u015f\u00fcnelim. Hi\u00e7 kimse bu problemin \u00e7\u00f6z\u00fcm\u00fc i\u00e7in bu zamana kadar polinom zaman algoritmas\u0131 bulamad\u0131. Bu y\u00fczden fakt\u00f6ring probleminin \u00e7ok daha zor oldu\u011fu d\u00fc\u015f\u00fcn\u00fcl\u00fcr ve bu problem \u201cNP\u201d (belirleyici olmayan polinom) karma\u015f\u0131kl\u0131k s\u0131n\u0131f\u0131na aittir. Daha zor \u201cNP\u201d problemleri i\u00e7in konu\u015fmak gerekirse, bilgisay\u0131msal ad\u0131mlar, girdilerin say\u0131s\u0131 ile beraber \u00fcstel fonksiyon olu\u015fturacak \u015fekilde artar; yakla\u015f\u0131k olarak 2n <\/sup>diyebiliriz. (\u00d6rne\u011fin, n=100 oldu\u011fu zaman, polinom fonksiyonumuz n2<\/sup>=1002<\/sup>=10.000 olur, fakat \u00fcstel fonksiyonumuz 2n<\/sup>=2100<\/sup> olur ve bu sonu\u00e7 polinom fonksiyonunun verdi\u011fi sonu\u00e7tan milyarlarca, trilyonlarca kat fazlad\u0131r.)<\/p>\n

Babai daha zorlu \u201cNP\u201d problemlerinin tayf\u0131n di\u011fer taraf\u0131ndaki kolay \u201cP\u201d problemlerine yakla\u015fabilece\u011fini g\u00f6sterdi.\u00a0 \u0130nsanlar\u0131n gribi yaymas\u0131n\u0131 veya organizmalar\u0131n i\u00e7indeki proteinlerin etkile\u015fimini temsil eden herhangi bir a\u011f (network), d\u00fcz \u00e7izgilerle birbirine ba\u011fl\u0131 ve birbirleriyle etkile\u015fim halinde noktalar, d\u00fc\u011f\u00fcmler (nodlar) k\u00fcmesi olarak tarif edilebilir. \u00c7\u00fcnk\u00fc d\u00fc\u011f\u00fcmler (nodlar) keyfi bir \u015fekilde yerle\u015ftirilebilir, ayn\u0131 ba\u011flant\u0131 d\u00fczenlemesine sahip iki grafik farkl\u0131 g\u00f6z\u00fckebilir (\u015fekildeki gibi), \u00f6zellikle grafik b\u00fcy\u00fcy\u00fcp karma\u015f\u0131k hale geldik\u00e7e.<\/p>\n

\u0130zomorfik graf probleminde zorluk iki grafi\u011fin ayn\u0131 olup olmad\u0131\u011f\u0131n\u0131 belirlemekti. Babai bug\u00fcn duyurdu\u011funa g\u00f6re; bu problemi \u00e7\u00f6zebilecek bir algoritma geli\u015ftirdi.<\/p>\n

Eugene Luks\u2019un, 1983 y\u0131l\u0131nda geli\u015ftirmi\u015f oldu\u011fu y\u00f6ntemde bilgisay\u0131msal ad\u0131mlar\u0131n say\u0131s\u0131, a\u011fdaki d\u00fc\u011f\u00fcmlerin say\u0131s\u0131 ile beraber \u00fcssel olarak art\u0131yordu. Babai\u2019nin algoritmas\u0131nda ise bilgisay\u0131msal ad\u0131mlar\u0131n say\u0131s\u0131, polinomial zamandan biraz h\u0131zl\u0131 olarak art\u0131yor. Grinin tonlar\u0131n\u0131 kar\u015f\u0131la\u015ft\u0131rmak gibi g\u00f6z\u00fckse de, uzmanlar i\u00e7in bu niteliksel fark heyecan verici. Aaronson\u2019un blo\u011funa bir okur, \u201cBu sonucun ge\u00e7erli oldu\u011funu varsayarsak, teorik bilgisayar biliminin \u00e7ok k\u0131ymetli bir yap\u0131ta\u015f\u0131 olabilir ve buna tan\u0131kl\u0131k etmek b\u00fcy\u00fcleyici bir \u015fey\u201d mesaj\u0131n\u0131 b\u0131rakt\u0131.<\/p>\n

Bug\u00fcnlerde networkler (a\u011flar) ve grafikler bakt\u0131\u011f\u0131m\u0131z her yerde olsa da, ironik bir bi\u00e7imde bu yeni algoritma bu kadar geni\u015f bir uygulama alan\u0131 bulamayabilir. Bunun nedeni, izomorfik graf problemindeki bir\u00e7ok grafi\u011fin \u015fu andaki algoritmalar ile zaten \u00e7\u00f6z\u00fclebilmesi. Aaronson, e\u011fer yeni algoritma \u00e7al\u0131\u015f\u0131rsa, \u015fu anki algoritmalar ile \u00e7\u00f6z\u00fclemeyen durumlar\u0131 \u00e7\u00f6zmeyi ba\u015faracaklar\u0131n\u0131 belirtiyor. Ayr\u0131ca yeni algoritma karma\u015f\u0131kl\u0131k teorisindeki en zorlu soruya, \u201cNP\u201d s\u0131n\u0131f\u0131n\u0131n ger\u00e7ekten \u201cP\u201d s\u0131n\u0131f\u0131ndan farkl\u0131 olup olmad\u0131\u011f\u0131 sorusuna cevap vermiyor. Ara\u015ft\u0131rmac\u0131lar genelde \u201cNP\u201d ve \u201cP\u201d s\u0131n\u0131f\u0131n\u0131n birbirlerinden farkl\u0131 olduklar\u0131n\u0131 d\u00fc\u015f\u00fcn\u00fcyor ve yan\u0131l\u0131rlarsa bir\u00e7ok \u015fey, \u00f6rne\u011fin internet \u015fifreleme teknikleri, inan\u0131lmaz bir \u015fekilde zarar g\u00f6rebilir. Fakat hen\u00fcz \u201cNP\u201d s\u0131n\u0131f\u0131n\u0131n \u201cP\u201d s\u0131n\u0131f\u0131na e\u015fit olmad\u0131\u011f\u0131n\u0131 g\u00f6steren bir kan\u0131t yok.<\/p>\n

Aaronson: \u201cYeni algoritmadaki as\u0131l ilerleme zor kategorideki -NP- ana problemi, kolay kategoriye -P- indirgemesi. \u0130zomorfik graf problemi tuhaf bir olguydu, zor oldu\u011funu d\u00fc\u015f\u00fcn\u00fcyorduk, ama yine de belli teorik \u00f6zelliklerle daha kolay problemlerle de ili\u015fkilendirebilece\u011fimizi biliyorduk. Bundan sonra problem bu kadar zor olmayabilir.\u201d<\/p>\n

Elbette di\u011fer ara\u015ft\u0131rmac\u0131lar da Babai\u2019nin \u00e7al\u0131\u015fmas\u0131n\u0131 incelemek zorunda. Aaronson, h\u00e2l\u00e2 \u00e7al\u0131\u015fman\u0131n detaylar\u0131n\u0131n incelenmesi gerekti\u011fini, Babai stat\u00fcs\u00fcndeki bir kimsenin bile hata yapabilece\u011fini belirtiyor.<\/p>\n

 <\/p>\n

\u00c7eviren: Semih Su\u00e7a\u011flar<\/strong><\/p>\n

Yeditepe \u00dcniversitesi Bili\u015fsel Bilimleri Y\u00fcksek Lisans Program\u0131<\/em><\/strong><\/p>\n

\u00a0<\/em><\/strong><\/p>\n

Kaynak:\u00a0<\/strong>Adrian Cho, \u201cMathematician claims breakthrough in complexity theory\u201d, http:\/\/news.sciencemag.org\/math\/2015\/11\/mathematician-claims-breakthrough-complexity-theory<\/a><\/p>\n

\u00a0<\/em><\/strong><\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

\u00a0G\u00f6rsel a\u00e7\u0131klamas\u0131: Yeni geli\u015ftirilen matematiksel algoritma izomorfik graf problemine meydan okuyor ve iki farkl\u0131 a\u011f\u0131n (network) kar\u015f\u0131la\u015ft\u0131r\u0131l\u0131p, bu iki a\u011f\u0131n asl\u0131nda ayn\u0131 olup olmad\u0131\u011f\u0131n\u0131n, daha \u00f6nce kullan\u0131lan algoritmalardan \u00e7ok daha az basamakta belirlenmesini sa\u011fl\u0131yor. Uyarlama Booya Bazooka.   Kompleksite teorisinde senelerden sonra en b\u00fcy\u00fck ilerleme s\u00f6ylentisi g\u00fcnlerdir internet ortam\u0131n\u0131 ayd\u0131nlat\u0131yor. L\u00e1szl\u00f3 Babai, \u015eikago \u00dcniversitesi\u2019nde matematik\u00e7i […]<\/p>\n","protected":false},"author":1,"featured_media":4132,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[19,1],"tags":[],"class_list":["post-4131","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-bilim-gundemi","category-genel"],"acf":[],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t