Bir hesaplama teorisinin dalı olarak karmaşıklık
Hesaplamalı karmaşıklıkteorisi, 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. Kaynak: tr.wikipedia.org/wiki/Hesaplamalı_karmaşıklıkteorisi.
Bir hesaplama probleminde prensip, algoritmada belirtilen matematiksel adımların mekaniğe uygulanması yoluyla probleme yaklaşmaktır. Ve bununla beraber hesaplamalı karmaşıklıkteorisindeki problemler, eşdeğer bir bilgisayar tarafından çözülebilen ortamlarda kullanılır.
Zorluk kaynağı olarak kaynak tüketimi
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şım karmaşıklığinde kullanılır), 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. Hesapalmalı karmaşıklıkteorisinin rollerinden biri, bilgisayarların yapabilecekleri ve yapmayacaklarını izah edip, pratikte ise bütün bunların sınırlarını belirlemektir.
Hesaplama teorisindeki konumu
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: algoritmada 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, hesapalmalı karmaşıklıkteorisi, uygun kısıtlanmış kaynaklarla çözülebilen veya çözülemeyen problemleri sınıflandırmaya çalışır.
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ı vardır.
Diğer importante 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.
Sorunun kapsamı
Bu çerçevede yalnızca hesapalmalı karmaşıklık teorisinin tanımı, kaynak tüketimi temelli zorluk kavramı ve sınıflandırma yaklaşımı ele alınmıştır. Deterministik kaos ve kendiliğinden düzenlenme (emergence) gibi konular bu kaynağa dayanmadığından burada yer almaz.
Bu açıklama Vikipedi kaynaklarından uyarlanmıştır ve şu lisans altında sunulur: CC BY-SA 4.0.
Bu gelişme hakkında düşüncelerinizi, donanım deneyimlerinizi veya sorularınızı Topluluk Forumumuzda paylaşın.
Foruma Katıl & Yanıtla ➔
İlk yorumu siz yazın
Fikrinizi bir kaynak, soru veya yapıcı karşı görüşle geliştirin.