P ve NP

P ve NP sınıflarının farkını öğrenirsin.

P ve NP

P, polinom zamanında çözülebilen problemler kümesidir. NP, verilen bir çözümün polinom zamanda doğrulanabildiği problemler kümesidir.

Her P problemi NP'dir. Ama NP'nin tümü P midir? Bu, bilgisayar biliminin en büyük açık sorunudur.

Doğrulama örneği

Bir dizinin sıralı olup olmadığını doğrulamak O(n)'dir: her komşu çifti karşılaştır. Bu yüzden sıralama denetimi P'dir.

Sıralı olup olmadığını doğrulayan bir fonksiyon, P sınıfına örnektir. Çözümü (sıralı diziyi) ver, anında doğrula.

Uygulama is_sorted fonksiyonu

is_sorted(arr) yaz. Dizinin sıralı olup olmadığını döndür. print(is_sorted([1, 2, 3])) ile True yazdır.

Örnek çözümü göster

def is_sorted(arr):
    # Dizi sıralı mı
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True
print(is_sorted([1, 2, 3]))

Kendini test et

NP problemlerinin ortak özelliği nedir?
- Polinom zamanda çözülür
- Çözümü polinom zamanda doğrulanır
- Çözümü yoktur
- Sadece döngüler içerir
Cevabı göster

Çözümü polinom zamanda doğrulanır — NP problemlerinin çözümü polinom zamanda doğrulanır.

sıralı koşulu

if arr[i] > arr[i + ____]:

Cevabı göster

if arr[i] > arr[i + 1]:

P ve NP: kavramları eşleştir

P

Çözülür
NP

Doğrulanır
P=NP

Açık sorun
polinom

Hızlı

Sıradaki ders: NP-complete

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler