Teorik bilgisayar bilimi ve matematikte hesaplama karmaşıklığı teorisi, hesaplama problemlerinin kaynak kullanımına göre sınıflandırılmasına ve bu sınıfların birbirleriyle ilişkilendirilmesine odaklanır. Hesaplamalı problem, bilgisayar tarafından çözülen bir görevdir. Bir hesaplama problemi, algoritma gibi matematiksel adımların mekanik olarak uygulanmasıyla çözülebilir.
Algoritma ne olursa olsun, çözümü önemli miktarda kaynak
gerektiriyorsa, bir problemin, doğası gereği, zor olduğu kabul edilir. Teori,
bu sorunları incelemek için matematiksel hesaplama modelleri sunarak ve
bunların hesaplama karmaşıklığını, yani bunları çözmek için gereken zaman ve
depolama gibi kaynakların miktarını ölçerek bu sezgiyi biçimlendirir.
İletişim miktarı (iletişim karmaşıklığında kullanılır), bir devredeki
kapı 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 ölçümleri de kullanılır.
Hesaplamalı karmaşıklık teorisinin rollerinden biri, bilgisayarların
yapabilecekleri ve yapamayacakları konusundaki pratik sınırları belirlemektir.
Yedi Milenyum Ödül Probleminden biri olan P'ye karşı NP problemi, hesaplama
karmaşıklığı alanına adanmıştır.
Teorik bilgisayar bilimindeki yakından ilişkili alanlar,
algoritmaların analizi ve hesaplanabilirlik teorisidir.
Algoritma analizi ile hesaplamalı karmaşıklık teorisi arasındaki temel
ayrım, birincisinin belirli bir algoritmanın bir sorunu çözmek için ihtiyaç
duyduğu kaynak miktarını analiz etmeye ayrılması, ikincisinin ise aynı sorunu
çözmek için çözülebilecek tüm olası algoritmalar hakkında daha genel bir soru
sormasıdır.
Daha doğrusu hesaplama karmaşıklığı teorisi, uygun şekilde kısıtlanmış
kaynaklarla çözülebilen veya çözülemeyen sorunları sınıflandırmaya çalışır.
Buna karşılık, mevcut kaynaklara kısıtlamalar getirmek, hesaplama
karmaşıklığını hesaplanabilirlik teorisinden ayıran şeydir: ikinci teori,
prensipte ne tür problemlerin algoritmik olarak çözülebileceğini sorar.
Hesaplamalı karmaşıklık teorisinde kullanılan bazı önemli karmaşıklık
sınıfları:
·
EXPSPACE, üstel uzayda deterministik bir Turing
makinesi tarafından çözülebilen tüm karar problemlerinin kümesidir.
·
EXPTIME (bazen EXP veya DEXPTIME olarak da
adlandırılır), deterministik bir Turing makinesi tarafından üstel zamanda
çözülebilen tüm karar problemlerinin kümesidir.
·
PSPACE, polinom miktarda uzay kullanan bir
Turing makinesi tarafından çözülebilen tüm karar problemlerinin kümesidir.
·
NP (deterministik olmayan polinom zamanı), karar
problemlerini sınıflandırmak için kullanılan bir karmaşıklık sınıfıdır.
·
P temel bir karmaşıklık sınıfıdır. Polinom
miktarda hesaplama süresi veya polinom süresi kullanılarak deterministik bir
Turing makinesi tarafından çözülebilecek tüm karar problemlerini içerir.
·
NL (deterministik olmayan logaritmik uzay),
logaritmik miktarda bellek alanı kullanılarak deterministik olmayan bir Turing
makinesi tarafından çözülebilen karar problemlerini içeren karmaşıklık
sınıfıdır.
https://en.wikipedia.org/wiki/Computational_complexity_theory
28 Ocak 2024
GERİ (matematik
anasayfa)
