NP (karmaşıklık)

P ve NP karmaşıklık sınıflarının bir diagramı Nen karar problemlerini içeren karmaşıklık sınıfıdır. Bu sınıftaki problemler belirli Turing Makinesi ile çokterimli zamanda doğrulanabilirler ve bu şekilde doğrulanabilen her problem NP sınıfındadır.

AI Kullan

İçindekiler

1. 10 ilişkiler: Alt küme toplamı problemi, Bağımsız küme problemi, Cook-Levin teoremi, Gezgin satıcı problemi, Hamilton yolu, Hamilton yolu problemi, Karmaşıklık, P (karmaşıklık), P ile NP arasındaki ilişki, Turing makinesi.

2. Karmaşıklık sınıfları

Alt küme toplamı problemi

Bilgisayar bilimlerinde, alt küme toplamı problemi karmaşıklık kuramında ve kriptografide önemli yeri olan bir problemdir. Karmaşıklık kuramında, problemin tanımı ve açıklaması basit ve anlaşılır olduğundan NP-Complete sınıfında yer alan problemleri anlayabilmek için iyi bir örnek oluşturmaktadır.

Görmek NP (karmaşıklık) ve Alt küme toplamı problemi

Bağımsız küme problemi

24 düğümlü bu çizgede en büyük bağımsız küme mavi olarak işaretlenmiş 9 düğümden oluşur. Bağımsız küme bir çizgede birbirleriyle komşu olmayan düğümleri içeren kümedir.

Görmek NP (karmaşıklık) ve Bağımsız küme problemi

Cook-Levin teoremi

SAT problemi bir NP-tam sınıfı problemidir.

Görmek NP (karmaşıklık) ve Cook-Levin teoremi

Gezgin satıcı problemi

Seyyar satıcı problemi yöneylem araştırması ve teorik bilgisayar bilimi alanlarında incelenen bir "kombinatorik optimizasyon" problemidir.

Görmek NP (karmaşıklık) ve Gezgin satıcı problemi

Hamilton yolu

8x8 ızgara graf Hamilton yolları üç örneği Hamilton Yolu, yönlü veya yönsüz bir grafta Hamilton yolu veya Hamilton devresinin olup olmadığının kararının verilmesinin problemidir.

Görmek NP (karmaşıklık) ve Hamilton yolu

Hamilton yolu problemi

Hamilton yolu problemi, Hamilton yolunun çözümü ile ilgili problemdir. İspat: Yönsüz graflarda Hamilton yolunun bulunması NP-tamdır (NP-complete) Hamilton Yolu (Hamiltonian Path): İspatta indirgeme (reduction) metodu kullanılacaktır.

Görmek NP (karmaşıklık) ve Hamilton yolu problemi

Karmaşıklık

Karmaşıklık, karmaşa veya kompleksite, anlaşılması güç parçalardan oluşan bir sistemi tanımlama yöntemine verilen addır. Bu ilişkilerin ortaya çıkarılması ağ kuramı ve ağ biliminin temel uğraş alanlarındandır.

Görmek NP (karmaşıklık) ve Karmaşıklık

P (karmaşıklık)

P, çokterimli zamanda (belirlenimli Turing Makinesi ile) çözülebilen karar problemlerini içeren karmaşıklık sınıfıdır. P sınıfı pek çok doğal problemi içerse de bazı önemli problemlerin (bk. NP) P içerisine girip girmediği bilinmemektedir.

Görmek NP (karmaşıklık) ve P (karmaşıklık)

P ile NP arasındaki ilişki

P harfi "polynomial", NP harfleri ise "non-deterministic polynomial" ifadelerini temsil eder, Türkçe karşılıkları "polinom" ve "belirleyici olmayan polinom"dur.

Görmek NP (karmaşıklık) ve P ile NP arasındaki ilişki

Turing makinesi

Turing makinesi temsili görünüm. Turing makinesi (İngilizce Turing machine), karmaşık matematiksel hesapların belirli bir düzenek tarafından yapılmasını sağlayan hesap makinesi.

Görmek NP (karmaşıklık) ve Turing makinesi

Ayrıca bakınız

Karmaşıklık sınıfları

• NP (karmaşıklık)
• NP-tam
• P (karmaşıklık)

Ayrıca bilinir Algoritmik zorluk derecesi, NP, NP-Tam, NP-Zor, NP-complete, NP-hard, Np complete, Np tam.

Ünionpedi bir ansiklopedi veya sözlük gibi organize bir kavram haritası veya semantik ağıdır. Her kavram ve ilişkileri kısa bir tanımını verir.

Bu kavram şemaları için bir temel olarak hizmet veren bir dev çevrimiçi zihinsel harita. Kullanımı ücretsiz ve her bir makale ya da belge indirilebilir. Bu öğretmenler, eğitimciler, öğrenciler ya da öğrenciler tarafından kullanılabilecek bir araç, kaynak veya çalışma, araştırma, eğitim, öğrenme veya öğretme referans var; akademik dünya için: okul, ilköğretim, ortaöğretim, lise, orta, kolej, teknik derece, kolej, üniversite, lisans, yüksek lisans veya doktora derecesi için; kağıtları, raporlar, projeler, fikirler, dokümantasyon, anketler, özetleri, ya da tez için. İşte tanım, açıklama, açıklama veya bilgi mi hangi her önemli anlamı ve bir sözlük olarak ilişkili kavramların bir listesidir. Türk, İngilizce, İspanyol, Portekizce, Japonca, Çince, Fransızca, Almanca, İtalyan, Lehçe, Flemenkçe, Rusça, Arapça, Hintçe, İsveççe, Ukrayna, Macarca, Katalan, Çek, İbranice, Danimarkalı, Fince, Endonezya, Norveççe, Romen, Vietnam, Koreli, Tay dili, Yunan, Bulgarca, Hırvat, Slovak, Litvanya dili, Filipinli, Letonca, Estonyalı ve Slovenya olarak mevcuttur. Yakında daha fazla dil.

Bilgiler Wikipedia makalelerine ve diğer Wikimedia projelerine dayanmaktadır ve Creative Commons Attribution-ShareAlike Lisansı kapsamında mevcuttur.

Ünionpedi, Wikimedia Vakfı tarafından onaylanmamıştır veya ona bağlı değildir.

Google Play, Android ve Google Play logosu Google Inc. kuruluşunun ticari markalarıdır.

Gizlilik Politikası