Hesaplama sorunu - Computational problem

Gelen teorik bilgisayar bilimleri , bir hesaplama problemi bir sorun da bu bilgisayar çözmek mümkün olabilir veya bir bilgisayar cevaplamak mümkün olabilir bir soru. Örneğin, faktoring sorunu

"Pozitif bir tam sayı Verilen n , bir aşikar olmayan asal çarpanı bulmak n ."

bir hesaplama problemidir. Bir hesaplama problem olarak görülebilir grubu arasında örnekleri ya da durumlarda birlikte ile muhtemelen boş, set çözeltiler her örneği / durum için. Örneğin, çarpanlara ayırma probleminde, örnekler n tamsayılarıdır ve çözümler , n'nin önemsiz asal faktörlerini tanımlayan p asal sayılarıdır .

Hesaplamalı problemler, teorik bilgisayar biliminde çalışmanın ana amaçlarından biridir. Hesaplamalı karmaşıklık teorisi alanı, belirli bir problemi çözmek için gereken kaynak miktarını ( hesaplama karmaşıklığı ) belirlemeye çalışır ve bazı problemlerin neden inatçı veya kararsız olduğunu açıklar . Hesaplama problemleri , çeşitli soyut makinelerle bunları hesaplamak (çözmek) için gereken kaynakları (örneğin zaman, uzay/bellek, enerji, devre derinliği) geniş bir şekilde tanımlayan karmaşıklık sınıflarına aittir . Örneğin, karmaşıklık sınıfı p cassical makineleri ve BQP kuantum makineleri.

Hem örnekleri hem de çözümleri ikili dizelerle , yani {0, 1} * öğeleriyle temsil etmek birçok sorun için tipiktir . Örneğin, sayılar ikili kodlama kullanılarak ikili dizeler olarak temsil edilebilir.

Türler

Bir karar problemi , her örnek için cevabın evet veya hayır olduğu bir hesaplama problemidir. Bir karar problemine bir örnek, asallık testidir :

" n pozitif bir tamsayı verildiğinde , n'nin asal olup olmadığını belirleyin ."

Bir karar problemi tipik olarak cevabı evet olan tüm örneklerin kümesi olarak temsil edilir . Örneğin, asallık testi sonsuz küme olarak gösterilebilir.

L = {2, 3, 5, 7, 11, ...}

Bir arama probleminde cevaplar rastgele dizgeler olabilir. Örneğin, çarpanlara ayırma, örneklerin pozitif tamsayılar (dize temsilleri) olduğu ve çözümlerin (dize temsilleri) asal sayılar topluluğu olduğu bir arama problemidir.

Bir arama problemi, arama ilişkisi adı verilen tüm örnek-çözüm çiftlerinden oluşan bir ilişki olarak temsil edilir . Örneğin, faktoring ilişki olarak temsil edilebilir.

R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}

tüm sayı çiftlerinden ( n , p ) oluşur; burada p , n'nin önemsiz bir asal çarpanıdır .

Bir sayma problemi , verilen bir arama probleminin çözümlerinin sayısını sorar. Örneğin, faktoring ile ilişkili bir sayma problemi

"Pozitif bir tam sayı Verilen n , bir aşikar olmayan asal faktörlerin sayısını saymak n ."

Bir sayma problemi, {0, 1} *' den negatif olmayan tam sayılara kadar bir f fonksiyonu ile temsil edilebilir . R arama ilişkisi için, R ile ilişkili sayma problemi fonksiyondur.

f R (x) = |{ y : R ( x , y ) }|.

Bir optimizasyon problemi , bir arama probleminin tüm olası çözümleri arasından "mümkün olan en iyi" çözümü bulmayı ister. Bir örnek maksimum bağımsız küme problemidir:

"Bir grafiktir göz önüne alındığında G , bir bulmak bağımsız set of G en büyük boyutu".

Optimizasyon problemleri arama ilişkileri ile temsil edilebilir.

Bir fonksiyon probleminde her girdi için tek bir çıktı ( toplam fonksiyondan ) beklenir, ancak çıktı karar probleminden daha karmaşıktır , yani sadece "evet" veya "hayır" değildir. En ünlü örneklerden biri gezgin satıcı problemidir:

"Şehirlerin bir listesi ve her şehir çifti arasındaki mesafeler verildiğinde, her şehri tam olarak bir kez ziyaret eden ve başlangıç ​​şehre dönen mümkün olan en kısa rotayı bulun."

Bu bir olan NP-zor problem optimizasyona önemli, yöneylem araştırması ve teorik bilgisayar bilimleri .

söz verme sorunu

Ana madde: Söz verme sorunu

Gelen hesaplama karmaşıklığı teorisi , genellikle üstü kapalı herhangi bir dize {0, 1} varsayılmaktadır * Söz konusu hesaplama sorunun bir örneğini temsil etmektedir. Ancak, bazen {0, 1} * dizelerinin tümü geçerli örnekleri temsil etmez ve bir tanesi "geçerli örnekler" kümesi olarak {0, 1} * 'nin uygun bir alt kümesini belirtir . Bu tür hesaplama problemlerine söz verme problemleri denir .

Aşağıda (karar) söz verme problemine bir örnek verilmiştir:

"Bir grafiktir göz önüne alındığında G , her belirlemek bağımsız ayar olarak G en çok 5 boyutuna sahiptir, ya da G, büyüklüğü, bağımsız bir dizi, en az 10 olan"

Burada geçerli örnekler, maksimum bağımsız küme boyutu en fazla 5 veya en az 10 olan grafiklerdir.

Karar vaadi problemleri genellikle {0, 1} *' nin ayrık alt kümeleri ( L evet , L hayır ) çiftleri olarak temsil edilir . Geçerli örnekler L evet ∪ L hayır içindekilerdir . L evet ve L hayır kimin cevap örneklerini temsil evet ve hayır sırasıyla.

Söz verme problemleri , yaklaşıklığın sertliği , özellik testi ve etkileşimli ispat sistemleri dahil olmak üzere , hesaplama karmaşıklığının çeşitli alanlarında önemli bir rol oynamaktadır .

Ayrıca bakınız

Notlar

Referanslar

  • Hatta Şimon ; Selman, Alan L. ; Yacobi, Yacov (1984), "Açık anahtarlı şifreleme uygulamalarıyla ilgili vaat problemlerinin karmaşıklığı", Information and Control , 61 (2): 159-173, doi : 10.1016/S0019-9958(84)80056-X.
  • Goldreich, Oded (2008), Hesaplamalı Karmaşıklık: Kavramsal Bir Perspektif , Cambridge University Press , ISBN 978-0-521-88473-0.
  • Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 Hesaplamalı Karmaşıklık", Gowers, Timothy'de ; Höyük-Yeşil, Haziran; Lider, Imre (ed.), The Princeton Companion to Mathematics , Princeton University Press, s. 575-604, ISBN 978-0-691-11880-2.