[MD-sorular] P = NP ile ilgili gelisme

[Ali Nesin]

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
>
>