Polinomsal Zaman

Kısaca: Polinomsal zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğuna göre en fazla bir polinom tane adımda çözebildiği bir problemdir. ...devamı ☟

Bu konuda henüz görüş yok.
Görüş/mesaj gerekli.
Markdown kullanılabilir.

Üstel zaman
6 yıl önce

üstel zaman polinomsal zamanı içine alabilir. Örneğin, gezgin satıcı problemini mümkün olan tüm turları teker teker hesaplayıp çözmek üstel zaman alacaktır...

Üstel zaman, Logaritmik zaman, NP-complete, Polinom, Polinomsal zaman, Seyyar satıcı problemi, Turing makinesi
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
Sabit zaman
6 yıl önce

Sabit zaman polinomsal zamanın bir alt kümesidir. Örneğin, bir sözcüğün ilk harfinin "a" olup olmadığını bulma problemi sabit zamanda çözülebilir. Algoritma...

Sabit zaman, Logaritmik zaman, NP-complete, Polinomsal zaman, Turing makinesi, Üstel zaman
Çokterimli zamanda indirgeme
6 yıl önce

Çokterimli zamanda indirgeme, bir problemi çokterimli (polinomsal) zamanda başka bir probleme dönüştürme işlemidir. Bu durumda, ikinci problemi çokterimli...

Çokterimli zamanda indirgeme, Polinomsal zaman, Ancak ve ancak, Gezgin Satıcı Problemi, Hamilton Çemberi Problemi
Lineer zaman
6 yıl önce

Lineer zaman, polinomsal zamanın bir alt kümesidir. Örneğin, iki kelimenin birbirinin tersi olup olmadığını anlama problemi lineer zamanda çözülebilir:...

Lineer zaman, Logaritmik zaman, NP-complete, Polinomsal zaman, Turing makinesi, Üstel zaman
P (karmaşıklık)
3 yıl önce

içerisine girip girmediği bilinmemektedir. Doğrusal programlama Eşleştirme problemleri Asallık testi İkili arama P ile NP arasındaki ilişki Polinomsal zaman...

P (karmaşıklık), Belirlenim, NP (karmaşıklık), P ile NP arasındaki ilişki, Polinomsal zaman, Turing Makinesi, Çokterimli, İkili arama, Asallık testi, Karmaşıklık, Eşleştirme problemleri
NP-Tam
6 yıl önce

sınıftaki problemler NP sınıfının en zor problemleridir. Bu problemleri polinomsal zamanda çözebilen algoritma bulunmamaktadır. İkili tatmin edilebilirlik Dolaşan...

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ı
NP (karmaşıklık)
3 yıl önce

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...

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ı