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.