Vikipedi, ozgur ansiklopedi
Karma?ıklık sınıfları arasındaki ili?kinin bir gosterimi.
Hesaplamalı karma?ıklık teorisi
, hesaplama problemlerini kendi zorluklarına gore sınıflandırmaya ve bu sınıfları birbirleriyle ili?kilendirmeye odaklanan teorik
bilgisayar bilimlerinde
hesaplama teorisinin bir dalıdır. Bir hesaplama probleminde prensip,
algoritmada
belirtilen
matematiksel
adımların
mekani?e
uygulanması yoluyla probleme yakla?maktır. Ve bununla beraber hesaplama karma?ıklık teorisindeki problemler, e?de?er bir
bilgisayar
tarafından cozulebilen ortamlarda kullanılır.
Kullanılan algoritma ne olursa olsun, cozumunde daha fazla kayna?a ihtiyac duyulursa, bu sorun do?al olarak zor olarak kabul edilir.
Teori
, bu problemleri incelemek icin matematiksel hesaplama modelleri geli?tirerek ve bunları cozmek icin ihtiyac duyulan zaman ve depolama gibi kaynakları nicelle?tirerek bu probleme ili?kin bir perspektif cizer. ?leti?im miktarı (ileti?im karma?ıklı?ında kullanılan), bir devredeki kapıların sayısı (devre karma?ıklı?ında kullanılır) ve
i?lemci
sayısı (paralel hesaplamada kullanılır) gibi di?er karma?ıklık onlemleri de kullanılır. Hesaplamalı karma?ıklık teorisinin rollerinden biri, bilgisayarların yapabilecekleri ve yapamayacaklarını izah edip, pratikte ise butun bunların sınırlarını belirlemektir.
Teorik bilgisayar bilimlerinde, algoritmalar ve
hesaplanabilirlik teorisi
analizi yakından ilgili alanlardır. Algoritmaların ve hesaplama karma?ıklı?ı teorisinin analizi arasındaki temel ayrım ise ?udur:
Algoritmalarda bir problemi cozmek icin belirli bir algoritma secilip, secilen algoritma icin ihtiyac duyulan kaynakların miktarı analiz edilir. Hesaplama karma?ıklı?ında ise, bir problemi cozmek icin kullanılabilecek olası tum algoritmalar ele alınarak,bunlar arasında sorular sorulur ve cozumlenmeye calı?ılır. Daha kesin bir ifadeyle, hesaplama karma?ıklı?ı teorisi, uygun kısıtlanmı? kaynaklarla cozulebilen veya cozulemeyen problemleri sınıflandırmaya calı?ır.
Bircok onemli karma?ıklık sınıfı, algoritma tarafından kullanılan zaman veya uzayı sınırlayarak tanımlanabilir. Bu ?ekilde tanımlanan karar problemlerinin bazı onemli karma?ıklık sınıfları ?oyledir:
| Karma?ıklık sınıfı
|
Hesaplama modeli
|
Kayna?ın sınırı
|
| Deterministik zaman
|
| DTIME
(
f
(
n
))
|
Deterministik Turing makinesi
|
Zaman
f
(
n
)
|
|
|
|
|
| P
|
Deterministik Turing makinesi
|
Zaman poly(
n
)
|
| EXPTIME
|
Deterministik Turing makinesi
|
Zaman 2
poly(
n
)
|
| Deterministik olmayan zaman
|
| NTIME
(
f
(
n
))
|
Deterministik olmayan Turing makinesi
|
Zaman
f
(
n
)
|
|
|
|
|
| NP
|
Deterministik olmayan Turing makinesi
|
Zaman poly(
n
)
|
| NEXPTIME
|
Deterministik olmayan Turing makinesi
|
Zaman 2
poly(
n
)
|
|
| Karma?ıklık sınıfı
|
Hesaplama modeli
|
Kayna?ın sınırı
|
| Deterministik uzay
|
| DSPACE
(
f
(
n
))
|
Deterministik Turing makinesi
|
Uzay
f
(
n
)
|
| L
|
Deterministik Turing makinesi
|
Uzay O(log
n
)
|
| PSPACE
|
Deterministik Turing makinesi
|
Uzay poly(
n
)
|
| EXPSPACE
|
Deterministik Turing makinesi
|
Uzay 2
poly(
n
)
|
| Deterministik olmayan uzay
|
| NSPACE
(
f
(
n
))
|
Deterministik olmayan Turing makinesi
|
Uzay
f
(
n
)
|
| NL
|
Deterministik olmayan Turing makinesi
|
Uzay O(log
n
)
|
| NPSPACE
|
Deterministik olmayan Turing makinesi
|
Uzay poly(
n
)
|
| NEXPSPACE
|
Deterministik olmayan Turing makinesi
|
Uzay 2
poly(
n
)
|
|
Di?er onemli karma?ıklık sınıfları arasında olasılık tabanlı
Turing makineleri
kullanılarak tanımlanan BPP, ZPP ve RP listelenebilir.Yine ornek olarak,
boolean
devreleri kullanılarak tanımlanan AC ve NC sınıfları ve
kuantum Turing makineleri
kullanılarak belirlenmi? BQP ve QMA sınıfları verilebilir.#P ise sayım problemlerinde kullanılan onemli ba?ka bir tur karma?ıklık sınıfıdır.ALL sınıfı ise butun kararların sınıfıdır.
