P, NP , Np-Complete, NP-Hard Nedir?

P

P, polinom zamanında çözülebilen tüm karar problemlerinin kümesini temsil eden bir karmaşıklık sınıfıdır . Yani polinom zamanı kullanarak deterministik bir Turing makinesi ile çözülebilen tüm karar problemlerini içerir .

Karar problemleri ne diyecek olursak herhangi bir matematiksel önermenin doğru ya da yanlış olduğuna karar verebilecek genel bir algoritma olup olmadığını sorar.

Turing makinesi ise karmaşık matematiksel hesapların belirli bir düzenek tarafından yapılmasını sağlayan hesap makinesi.

P problemlerini o zaman yeniden tanımlayacak olursak eğer polinom zamanda sonucun doğru ya da yanlış olduğunu belirleyebildiğimiz ve karmaşık hesapların çözüldüğü bir karmaşıklık problemi sınıfıdır.

P problemlerine örnek verecek olursak ;

• Toplama işlemi
• Sayının asal olup olmadığı
• En büyük ortak bölen bulma
• Sıralı bir liste içinde arama yapma
• Bir y doğal sayısının tek sayı olup olmaması

NP

Belirlenimsiz problemler sınıfı ; cevabın “doğru” olduğu olayların, rasyonel olarak doğrulanabilir kanıtları olan karar problemlerinden oluşur. Bu kanıtlar, polinomsal zamanda yapılacak rastgele olmayan hesaplamalar ile doğrulanabilir olmalıdır.

NP problemleri en büyük karmaşıklık sınıflarından biridir. Günümüzde NP problemleri için verimli kabul edilebilecek bir algoritma bulunamamıştır. NP problemini bir de Sudoku üzerinde düşünelim;

Sudoku, bazı kutucukları doldurulmuş şekilde verilen ve tüm kutucukların doldurulması için çeşitli kurallar dizisi bulunan, ‘n x n’ sayıda kutucuktan oluşan bir oyundur. Kurallarına uygun düzgün bir sudoku için en az bir doğru cevap olduğu kesindir. Bu cevap verilen kurallar dizisi altında kolayca doğrulanabilir. Aynı kurallar dizisine sahip farklı boyuttaki sudokularında cevabı kontrol etmek için gereken adımlar polinomsal olarak değişmektedir. Sudoku boyutu artıkça, çözüm için gereken adımlar da üstel olarak artmaktadır. Adım sayısı arttıkça da problemin çözüm süresi aynı oranda artmaktadır.

Yani NP problemlerine kısaca polinomsal zamanda doğrulanabilecek karmaşıklık sınıfı problemleridir diyebiliriz.

P ve Np arasındaki ilişkiye bakacak olursak;

P, polinomsal zamanda çözülebilecek problemler sınıfını oluşturur. NP ise, çözümü polinomsal zamanda doğrulanabilecek problemler sınıfını oluşturur.

P, NP kümesinin alt sınıfıdır.

Bu iki problemin ortak noktası ikisinin de karar problemlerinden oluşmasıdır.

NP- Complete

NP sınıfında yer alan bazı problemler o kadar zordur ki onlar için polinom zamanı bulma girişimleri çok uzun çabalardan sonra sonuçsuz kalmıştır ve NP-Complete sınıfı oluşmuştur. Bu problem sınıfının özelliği ise şudur: NP kümesindeki diğer her problem bu kümedeki problemlere indirgenebilir.

NP-Complete problemine örnekler: Bir grafın Hamilton döngüsüne sahip olup olmadığını belirleme, Boolean formülünün tatmin edici olup olmadığını belirleme

NP-Hard

Buradaki problemlerin çözümü en az NP -Complete kümesindekiler kadar zordur. Diğerlerinden farkı ise karar problemlerinden oluşma zorunluluğu taşımamasıdır. Burada da NP -Complete kümesindeki problemler NP -hard kümesindekilere indirgenebilir.

NP-Hard problemine örnekler: Gezgin Satıcı problemi, Durma(Halting) problemi, Vertex cover Problemi, Circuit-satisfiability problemi

NP-Hard ve NP-Complete arasındaki fark

• NP- Hard problemler polinom zamanda NP-Complete problemlerine indirgenebiliyorsa çözülürken, NP-complete problemleri polinom zamanda deterministik olmayan bir Turing makinası ile çözülebilir.
• NP-Hard problemini çözmek için NP problem sınıfı içinde olmak zorunda değilken NP-Complete problemini çözmek için hem NP hem de NP-Hard problemler sınıfında olmak zorundadır.
• NP-Hard karar problemi değilken, NP-Complete karar problemidir.

Bilgisayar bilimcilerinin ve matematikçilerin 1971 yılından beri uğraştığı problem:

P=NP mi yoksa P≠NP mi ?

Clay Matematik Enstitüsü tarafından seçilen yedi Milenyum Ödül Probleminden biridir ve ilk doğru çözüm için 1.000.000 ABD Doları tutarında bir ödül taşır.

Bu problemi şöyle tanımlayabiliriz:

• Her NP problemi P problemine indirgenebilir mi?
• Her problem için polinomsal zamanda çözülebilir bir algoritma bulunabilir mi?

Kimse şu ana kadar bu sorunun cevabını kanıtlayamadı. Bilgisayar bilimcilerin ve matematikçilerin uzun yıllardan beridir çözmeye çalıştığı bir problemdir ve çoğunluk denklemin eşitsizliğinden yanadır.

P=NP durumunun doğrulanması demek bütün internet güvenliğinin altüst edebileceği demektir. Çünkü kriptografi imkansız hale gelir ve bununla birlikte internette her türlü gizlilik veya doğrulanabilirlik olur.

Bu problemi Scott Aaronson şu sözleriyle ifade etmek de mümkün;

Eğer P = NP ise, dünya bizim varsaydığımızdan çok daha farklı bir yer olurdu. “Yaratıcı sıçramaların” özel bir değeri olmayacak, bir problemi çözme ile çözümü bulduktan sonra fark etme arasında temel bir boşluk olmayacaktı. Bir senfoniyi takdir edebilecek herkes Mozart olurdu; adım adım bir argümanı takip edebilen herkes Gauss olurdu.

— Scott Aaronson .