Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
102 kez görüntülendi
Amatör olarak P NP problemiyle ugraşmayı düşünüyorum.Fakat hangi temel dersleri önkoşul olarak bilmeliyim.Bildiğim kadarıyla hesaplamalı karmaşıklık teorisi,algoritmalar vb. konular var fakat yinede genel olarak bir liste yapıp tümünü öğrenip o şekilde çözüme gitmeye çalışacağım.

Ayrıca bu soru için şöyle birşey duymuştum.Galiba 1 tane np roblemi bile p diline indirgenebilirse ,tüm npler p ye indirgenebilir oluyordu.Bunun tersi içinde bir tane np problemin p ye hiçbir zaman indirgenemeyeceği ispatlanırsa bütün npler np olmak zorunda olur mu?Çünkü eğer bir np problemin p olamayacağını ispatlarsak ardında atıyorum bir tane np inin p ye indirgenmesi çelişki olur.Çünkü hepsi p olmak durumunda olur ama biz bir tanesinin olamayacağını göstermiştik.

Ben çalışmalarımda p ile np nin eşit olmadığını göstermek için uğraşacağım.Bunun içinde np lerden birinin (mesela subset problem)hiçbir zaman p ye indirgenemeyeceğini ispatlamaya çalışacağım.

Verilecek bilgiler için şimdiden teşekkürler.
Akademik Matematik kategorisinde (58 puan) tarafından 
tarafından yeniden gösterildi | 102 kez görüntülendi

$P$ ne demek? $NP$ ne demek ?

su linkte soyle kenarda dursun

https://complexityzoo.uwaterloo.ca/Complexity_Zoo

Icinde konu ile ilgili makaleler (hem baslangic hem de ileri seviye icin) ve daha genel karmasiklik hiyerarsisini gorebilirsiniz. $P$ ve $NP$ nedense karmasiklik teorisinin jonu olmus ama yardimci oyuncular da bu o kadar onemli bence.

18,741 soru
20,913 cevap
68,607 yorum
21,131 kullanıcı