Hesaplamalı karmaşıklık teorisi

Hesaplamalı karmaşıklık teorisi, hesaplama problemlerini kendi zorluklarına göre 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 çözülebilen ortamlarda kullanılır.

Kullanılan algoritma ne olursa olsun, çözümünde daha fazla kaynağa ihtiyaç duyulursa, bu sorun doğal olarak zor olarak kabul edilir. Teori, bu problemleri incelemek için matematiksel hesaplama modelleri geliştirerek ve bunları çözmek için ihtiyaç duyulan zaman ve depolama gibi kaynakları nicelleştirerek bu probleme ilişkin bir perspektif çizer. İ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 önlemleri de kullanılır. Hesaplamalı karmaşıklık teorisinin rollerinden biri, bilgisayarların yapabilecekleri ve yapamayacaklarını izah edip, pratikte ise bütün 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 çözmek için belirli bir algoritma seçilip, seçilen algoritma için ihtiyaç duyulan kaynakların miktarı analiz edilir. Hesaplama karmaşıklığında ise, bir problemi çözmek için kullanılabilecek olası tüm algoritmalar ele alınarak,bunlar arasında sorular sorulur ve çözümlenmeye çalışılır. Daha kesin bir ifadeyle, hesaplama karmaşıklığı teorisi, uygun kısıtlanmış kaynaklarla çözülebilen veya çözülemeyen problemleri sınıflandırmaya çalışır.

 Önemli karmaşıklık sınıfları 
Birçok önemli 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ı önemli karmaşıklık sınıfları şöyledir:
Karmaşıklık sınıfıHesaplama modeliKaynağın sınırıDeterministik zamanDTIME(f(n))Deterministik Turing makinesiZaman f(n)PDeterministik Turing makinesiZaman poly(n)EXPTIMEDeterministik Turing makinesiZaman 2poly(n)Deterministik olmayan zamanNTIME(f(n))Deterministik olmayan Turing makinesiZaman f(n)NPDeterministik olmayan Turing makinesiZaman poly(n)NEXPTIMEDeterministik olmayan Turing makinesiZaman 2poly(n)Karmaşıklık sınıfıHesaplama modeliKaynağın sınırıDeterministik uzayDSPACE(f(n))Deterministik Turing makinesiUzay f(n)LDeterministik Turing makinesiUzay O(log n)PSPACEDeterministik Turing makinesiUzay poly(n)EXPSPACEDeterministik Turing makinesiUzay 2poly(n)Deterministik olmayan uzayNSPACE(f(n))Deterministik olmayan Turing makinesiUzay f(n)NLDeterministik olmayan Turing makinesiUzay O(log n)NPSPACEDeterministik olmayan Turing makinesiUzay poly(n)NEXPSPACEDeterministik olmayan Turing makinesiUzay 2poly(n)
Diğer önemli karmaşıklık sınıfları arasında olasılık tabanlı Turing makineleri kullanılarak tanımlanan BPP, ZPP ve RP listelenebilir.Yine örnek 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 önemli başka bir tür karmaşıklık sınıfıdır.ALL sınıfı ise bütün kararların sınıfıdır.

Kategori:Teorik bilgisayar bilimi