[Turkmath:2497] Re: Mathematicians Race to Debunk German Man Who Claimed to Solve One of the Most Important Computer Science Questions of Our Time

[yilmaz akyildiz]

LÜTFEN bu mesajı bu işlerle uğraşan matematikçi arkadaşlar okumasınlar!

Nedeni: montanalı fizikçimiz Recep Avcı nın sorusunu bilal e anlatır gibi
açıklayacağım...

recep in sorusu şu

her bilgisyar programının yani algoritmaların çözüm süreci (zaman) acaba
data nın boyu cinsinden bir polinom ifadeden hesaplanabilirmi?

örnek:
diyelim ki n tane insan var ve biz bu insanların yaşlarının ortalamasını
bulmak istiyoruz.
bir program yazdık (gayet basit, yaşları topla ve n ye böl)
bu program makinada bu işlemi ne kadar zamanda yapar.
bunun hesabı kolaydır.
biz örnek olarak diyelim ki,  (kafadan atıyorum):
bu zaman şu ifade ile verilir: n^2 - n +1
örneğin, bu formül diyor ki 10 tane insanın yaş ortalamasını bu program
 100-10+1 = 91 mili saniyede hesaplayabiliyor.
n^2 - n +1 bir polinomdur. Lise polinomu. hani çarpanlara çurpanlara
ayırır, kök mök bulurduk.

bir milyon dolarlık soru şu:
acaba bütün bilgisayar problemleri için harcanan zamanı datanın boyutu
cinsinden bir polinomdan hesaplayabilirmiyiz?
öyle ya başka fonksiyonlar da var, örneğin üstel fonksiyonlar var,
trigonommetrik fonksiyonlar var..

şimdi recepğ in gönderdiği şu haber diyor ki
Bonn dan bir alman matematikçi bunun böyle olmadığını, yani öyle problemler
var ki onların bilgisayarda harcayacakları zaman için asla bir polinom
ifade bulamazsınız! bu bir yokluk problemidir. yani adam ispatlamış (?!) ki
elimizde şu an öyle problemler var ki (en bilineni ve standardı
 TSP:Travelling Salesman Proplem) şu ana kadar bunun için polinomla çalışan
algoritma bulunamadığı gibi yarın da bulunamayacaktır!

teorik bilgisayar biliminin de kendisine göre bir unification (denklik)
teoremi vardır ve bence o bilimin en enteresan konusu budur:
polinom zamanda çözümlenemeyen problemler birbirlerine şu anlamda
denktirler:
birisini polinam zamanda çözebilirseniz diğerlerini de polinom zamanda
çözebilirsiniz.

arkadaşlar: ben bu konunun eksperi değilim. dolayısı ile yukarda
yanlış-eksik bir şeyler dedimse kabahat benim değil bilal in dir! eminim
memleketimizde de bu konuyo çok iyi takip eden arkadaşlarımız var (örneğin
Bilkent de Osman Oğuz, ve hatta internet dedemiz Mustafa Akgül de bu
konulardan gelmedir, ama biz 68 lerden geçti artık bu işler, gençlere
sesleniyorum...)

2017-08-31 16:22 GMT+03:00 Avci, Recep <avci at montana.edu>:

https://motherboard.vice.com/en_us/article/evvp34/p-vs-np-
> alleged-solution-nortbert-blum
>
> ---
> Yilmaaaz
>
> Bu haberi duydun mu?
>
> Recep
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://yunus.listweb.bilkent.edu.tr/pipermail/turkmath/attachments/20170901/a50bea94/attachment.html>