Hesaplamalı karmaşıklık teorisi

Karmaşıklık sınıfları arasındaki ilişkinin bir gösterimi.

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