[MD-sorular] P = NP ile ilgili gelisme

[tibet efendi]

NP kümesi, non-deterministik bir makinayla (misal Turing Makinasi) polinomial zamanda hesaplanabilen problemlerin kümesidir.
Burada kullandigim kavramlari tek tek acmam gerekiyor. Özetle biraz bahsedecegim. Teknik tanimlarini yapmadan.
non-deterministik makina (ya da algoritma): Böyle bir makina yoktur. Bunlara medyumlu (oracle) makinalar denir. Teorik makinalardir. Bunlar icin yazilmis algoritmalar normal algoritmalara benzemez. Ayni anda bir cok sey yapmasini söylersiniz programa. Program da hep ise yarayani yapar. Bunu cift cekirdekli islemci gibi de düsünebilirsiniz. n cekirdekli islemci! Ayni anda n tane islemi yürütebiliyor. n sonlu olmak zorunda ama istediginiz kadar büyük olabilir. Programiniza göre degisir bu.
P=NP? de su sorudur: Nondeterministik bir makinada polinomial zamanda cözebildigimiz her problemi normal yani deterministik bir makinada da polinomial zamanda cözebilir misiniz? Bu sorunun cevabi bilinmiyordu. Hala da bilinmiyor anladigim kadariyla.
Bunu Ali Nesin'in dedigi gibi de yorumlayabilirsiniz.
"Problem" lafini da kisaca aciklayayim. Teorik bilgisayar biliminde "problem" deyince dogal sayilarin bir altkümesi anlasilir. Görsel de olsa problemler, dogal sayilarla kodlanarak dogal sayilarin altkümeleri seklinde ifade edilir.Bir sayinin o altkümeye ait olup olmadigina karar vermeye de "problemi cözmek" deniyor. Birkac örnek görürseniz hemen anlarsiniz. Böyle anlatinca zor bir sey oldugunu sanilabilir. Zor degil.
tibet


--- On Sat, 8/14/10, Ali Nesin <anesin at nesinvakfi.org> wrote:

From: Ali Nesin <anesin at nesinvakfi.org>
Subject: Re: [MD-sorular] P = NP ile ilgili gelisme
To: "zati lokum" <zati.lokum at gmail.com>
Cc: "md"
 <md-sorular at matematikdunyasi.org>
Date: Saturday, August 14, 2010, 5:42 PM

Bildigim kadariyla problem su:
Diyelim n dogal sayisiyla ilgili bir problem icin programlarin en kisasini yazdin.
Yanit belli bir zaman sonra cikti. Bu zamana f(n) diyelim.
Verilmis yanitin dogru olup olmadigini da diyelim g(n) zamanda anliyoruz.
g(n) < f(n) olmali elbet.
Mesela bir sayiyi asal carpanlarina ayirmak kolay degildir. Ama asal sayilari carpinca verilen sayinin elde edilip edilmedigini anlamak cok kolaydir.
Mesela bir grafta her koseden tek bir defa gecen bir yol bulmak zor olabilir, ama verilen bir yolun bu kosula uyup uymadigini anlamak cok kolaydir.
f(n)'nin g(n)'den cok cok buyuk olmamasini dileriz dogal olarak.
Cevabin dogrulugunu kontrol etmekten cok cok daha fazla zaman almamali dogru cevabi bulmak.
Bir p polinomu icin p(g(n)) > f(n) ise, mutlu oluruz. (Yani Polinomiyal, yani
 P)
Boyle
 bir polinomun olmamasi, f(n)'nin g(n)'ye gore en az eksponansiyel oldugunu soyler. (Yani Non-Polinomiyal, yani NP)
Soru, boyle bir polinomun olup olmadigi.
Galiba genel kani olmadigi yonunde.
Hatam varsa bilen biri duzeltsin.
A


zati lokum wrote:
> Bu problem tam olarak neyi söylüyor, getirisi nedir?
>  Zati Lokum
> 
> 2010/8/10 Gorkem Ozkaya <gorkemozkaya at gmail.com <mailto:gorkemozkaya at gmail.com>>
> 
>     Matematikci Vinay Deolalikar, P != NP'yi kanitladigini iddia eden
>     calismasinin taslak metnini yayimlamis.    Terence Tao'nun konuyla
>     ilgili yazisi:
> 
>     http://www.google.com/buzz/114134834346472219368/1vfSCPtRQZf/Vinay-Deolaikar-recently-released-a-102-page
>     _______________________________________________
>     MD-sorular e-posta listesi
>     sorular at matematikdunyasi.org <mailto:sorular at matematikdunyasi.org>
>     http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
> 
>
 

_______________________________________________
MD-sorular e-posta listesi
sorular at matematikdunyasi.org
http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular



      
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20100817/7debff51/attachment.htm>