NP-complete ile ilgili bilgilerin yer aldığı sayfamız: NP
Np-Complete
Kısaca: NP, belirsiz Turing Makinesi ile çokterimli (polinomsal) zamanda çözülebilen 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. ...devamı ☟
Bu konuda henüz görüş yok.
NP (karmaşıklık)
3 yıl öncezamanda çözülebilir. NP-Tam (NP-complete), hem NP olup hem NP-Zor olan problemlerin sınıfıdır. Dolayısıyla bu sınıftaki problemler NP sınıfının en zor problemleridir...
NP (karmaşıklık), Belirsiz Turing Makinesi, Dolaşan satıcı, P (karmaşıklık), P ile NP arasındaki ilişki, Turing Makinesi, Çokterimli, Çokterimli zamanda indirgeme, Hamilton dönüşü, Hamilton yolu, Altküme toplamıPolinomsal zaman
3 yıl öncezaman, daha basit bazı zamanlara ayrılabilir: Sabit zaman Lineer zaman İkinci derece zaman vs. Ayrıca bakınız: Logaritmik zaman, Üstel zaman, NP-complete...
Polinomsal zaman, Lineer zaman, Logaritmik zaman, NP-complete, Sabit zaman, Turing makinesi, Üstel zamanAlt Küme Toplamı Problemi
6 yıl önceproblemi NP-Complete sınıfında yer almaktadır. Bir dilin NP-Complete sınıfına ait olduğunu göstermek için; Dilin, NP sınıfında yer aldığını, NP sınıfında...
Logaritmik zaman
6 yıl önce\log(n)\,} civarı adımda çözebildiği bir problemdir. Örneğin, ikili arama algoritması logaritmik zamanda çalışır. Polinomsal zaman Üstel zaman NP-complete...
Logaritmik zaman, NP-complete, Polinomsal zaman, Turing makinesi, Üstel zaman, İkili aramaÜstel zaman
6 yıl önceçözmek üstel zaman alacaktır, zira n {\displaystyle n\,} şehir için n ! {\displaystyle n!\,} tur vardır... Logaritmik zaman Polinomsal zaman NP-complete...
Üstel zaman, Logaritmik zaman, NP-complete, Polinom, Polinomsal zaman, Seyyar satıcı problemi, Turing makinesiKâhinli Turing makinesi
7 yıl önceşeritlerini okuma ve değiştirme hakkı vardır. Kâhinli Turing makinesi, NP-complete problem indirgemesi yapılırken kullanılır, zira bir problemin (yani kâhinin)...
Lineer zaman
6 yıl önceiçin 2 n {\displaystyle 2n\,} adımda bitecek ve iki kelimenin birbirinin tersi olup olmadığını söyleyecektir. Logaritmik zaman Üstel zaman NP-complete...
Lineer zaman, Logaritmik zaman, NP-complete, Polinomsal zaman, Turing makinesi, Üstel zamanHamilton yolu problemi
6 yıl önceproblemdir. İspat: Yönsüz graflarda Hamilton yolunun bulunması NP-tamdır (NP-complete) Hamilton Yolu (Hamiltonian Path): • Bir graftaki her düğümden (node)...