[MD-sorular] P = NP ile ilgili gelisme

[Burak Kaya]

Küçük bir düzeltme. Oracle makineleri ile non-deterministic Turing
makineleri farklı şeylerdir.

Non-deterministic Turing makinelerinin temel özelliği geçiş fonksiyonunun
aslında bir fonksiyon değil bir bağıntı olmasıdır. Yani, deterministik bir
Turing makinesi, mesela, sadece "a durumunda 2 okursan b durumuna geç" gibi
bir kural barındırabilir ama bir non-deterministic makine "a durumunda 2
okursan b durumuna geç" ve "a durumunda 2 okursan c durumuna geç"
kurallarının ikisini de aynı anda barındırabilir. Bu da sizin dediğiniz
"aynı anda n tane işlem yürütme"ye denk geliyor zaten. Herneyse...

Oracle makineleri çok özel Turing makineleridir. Bu makinelerin standart
Turing makinelerinden farkı, kendisine verilen herhangi bir string'in
belirli bir dile ait olup olmadığını *tek* bir adımda söyleyen bir oracle'a
sahip olmaları. Mesela doğal sayıların hesaplanamaz bir A alt kümesini
alalım. A için oracle'a sahip bir oracle makinesi (yani verilen bir doğal
sayının A'da olup olmadığına tek bir adımda karar verebilen bir makine) A'yı
ve A'nın "bilgisi" ile hesaplanabilen bir çok hesaplanamaz kümeyi
hesaplayabilir, ama standart bir Turing makinesi bunu yapamaz
(hesaplanamazlık tanımı gereği!).

Non-deterministic Turing makinelerinin hesaplama güçleri (yani tanıdıkları
diller) deterministik Turing makinelerininki ile aynıdır ama oracle
makineleri (artık hangi dil için bir oracle'a sahiplerse) duruma göre çok
daha güçlü hesaplamalar yapabilir.

17 Ağustos 2010 21:58 tarihinde tibet efendi <tibetefendi at yahoo.com> yazdı:

> 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
>
>
>
> _______________________________________________
> MD-sorular e-posta listesi
> sorular at matematikdunyasi.org
> http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
>



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