Azaltma (karmaşıklık) - Reduction (complexity)

Boolean tatmin edilebilirlik probleminden ( AB ) ∧ ( ¬ A ∨ ¬ B ∨ ¬ C ) ∧ (¬ ABC ) bir tepe örtüsü problemine indirgeme örneği . Mavi köşeler minimum bir köşe örtüsü oluşturur ve gri ovaldeki mavi köşeler , orijinal formül için tatmin edici bir doğruluk atamasına karşılık gelir .

Gelen Hesaplama teorisi ve hesaplama karmaşıklığı teori , bir indirgeme bir bir algoritma bir dönüştürme sorun başka bir sorun haline. Bir problemden diğerine yeterince verimli bir indirgeme, ikinci problemin en az birincisi kadar zor olduğunu göstermek için kullanılabilir.

Sezgisel olarak, problem B'yi verimli bir şekilde çözmek için bir algoritma (eğer varsa), problem A'yı verimli bir şekilde çözmek için bir alt rutin olarak kullanılabilirse , problem A , problem B'ye indirgenebilir . Bu doğru olduğunda, A'yı çözmek B'yi çözmekten daha zor olamaz . "Daha zor", belirli bir bağlamda gerekli hesaplama kaynaklarının daha yüksek bir tahminine sahip olmak anlamına gelir (örneğin, daha yüksek zaman karmaşıklığı , daha fazla bellek gereksinimi, tek iş parçacıklı bir çözüme kıyasla paralel bir çözüm için ekstra donanım işlemci çekirdeklerine yönelik pahalı ihtiyaç, vb.) . Bir indirgeme varlığı A için B , gösterim kestirme yazılabilir Am B (m, genellikle redüksiyon tipi kullanılan göstermek için ≤ bir simge ile, eşleştirme azalma , s: polinom azalma ).

Belirli bir tip azalmalara problemlerin bir dizi oluşturulan matematiksel yapısı genellikle oluşturan ön sipariş olan, denklik sınıfları tanımlamak için kullanılabilir unsolvability derecelerde ve karmaşıklık sınıfları .

Tanıtım

İndirimleri kullanmamız gereken iki ana durum vardır:

  • İlk olarak, kendimizi daha önce çözdüğümüz bir probleme benzer bir problemi çözmeye çalışırken buluruz. Bu durumlarda, genellikle yeni sorunu çözmenin hızlı bir yolu, yeni sorunun her örneğini eski sorunun örneklerine dönüştürmek, bunları mevcut çözümümüzü kullanarak çözmek ve sonra bunları nihai çözümümüzü elde etmek için kullanmaktır. Bu belki de indirimlerin en belirgin kullanımıdır.
  • İkincisi: Diyelim ki çözülmesi zor olduğunu kanıtladığımız bir problemimiz var ve buna benzer yeni bir problemimiz var. Çözmenin de zor olduğundan şüphelenebiliriz. Çelişkiyle tartışıyoruz: yeni sorunun çözülmesinin kolay olduğunu varsayalım. O zaman, eski problemin her örneğini, yeni problemin örneklerine dönüştürerek ve bunları çözerek kolayca çözülebileceğini gösterebilirsek, bir çelişki var demektir. Bu, yeni sorunun da zor olduğunu ortaya koyuyor.

Bir azalmanın çok basit bir örnek, bir çarpma için kare alma . Diyelim ki tüm bildiğimiz toplama, çıkarma, kare alma ve ikiye bölme. Bu bilgiyi aşağıdaki formülle birleştirerek herhangi iki sayının çarpımını elde etmek için kullanabiliriz:

Diğer yönde de bir azalma var; Açıkçası, eğer iki sayıyı çarpabilirsek, bir sayının karesini alabiliriz. Bu, bu iki sorunun eşit derecede zor olduğunu ima ediyor gibi görünüyor. Bu tür bir indirgeme Turing indirgemesine karşılık gelir .

Ancak, kare alma işlevini yalnızca bir kez ve yalnızca sonunda kullanabileceğimiz kısıtlamasını eklersek, indirgeme çok daha zor hale gelir. Bu durumda, çarpma dahil tüm temel aritmetik işlemleri kullanmamıza izin verilse bile, genel olarak hiçbir indirgeme yoktur, çünkü istenen sonucu bir kare olarak elde etmek için önce karekökünü ve bu kareyi hesaplamamız gerekir. kök bir olabilir irrasyonel sayı gibi bu rasyonel sayılar üzerinde aritmetik işlemleri tarafından inşa edilemez. Ancak diğer yöne gidersek, bir sayının karesini kesinlikle sadece bir çarpma ile alabiliriz, sadece sonunda. Bu sınırlı indirgeme biçimini kullanarak, çarpmanın genel olarak kare almaktan daha zor olduğu şaşırtıcı olmayan sonucu gösterdik. Bu çok-bir azalmaya karşılık gelir .

Özellikler

Bir azalma meydana olan preordering a,, dönüşlü ve geçişli ilişki ile, P ( N ) x P ( N ), P ( N ) 'dir güç grubu bir doğal sayılar .

İndirgeme türleri ve uygulamaları

Yukarıdaki örnekte açıklandığı gibi, hesaplama karmaşıklığında kullanılan iki ana indirgeme türü vardır, çok-bir indirgeme ve Turing indirgemesi . Birçok kimse azalmalar harita örneklerini bir problemin örneklerini diğerinin; Turing indirgemeleri , diğer sorunun çözülmesinin kolay olduğunu varsayarak, bir sorunun çözümünü hesaplar . Çok-bir indirgeme, Turing indirgemenin daha güçlü bir türüdür ve sorunları farklı karmaşıklık sınıflarına ayırmada daha etkilidir. Bununla birlikte, çoklu indirimler üzerindeki artan kısıtlamalar, onları bulmayı daha da zorlaştırıyor.

Bir sorun tam sınıfındaki her sorunun bu soruna azaltır eğer bir karmaşıklık sınıf için ve o sınıfın kendisi aynı zamanda. Bu anlamda problem sınıfı temsil eder, çünkü ona yönelik herhangi bir çözüm, indirgemelerle birlikte sınıftaki her problemi çözmek için kullanılabilir.

Ancak, faydalı olması için indirimlerin kolay olması gerekir . Örneğin , boolean tatmin edilebilirlik problemi gibi çözülmesi zor NP-tamamlanmış bir problemi, bir sayının sıfıra eşit olup olmadığını belirlemek gibi önemsiz bir probleme, indirgeme makinesinin problemi üstel zamanda çözmesini ve çıktının sıfır olmasını sağlayarak oldukça mümkündür. sadece bir çözüm varsa. Ancak bu pek bir şey sağlamaz, çünkü yeni problemi çözebilsek bile, eski problemi çözmek kadar indirgemeyi yapmak da zordur. Benzer şekilde, hesaplanamayan bir işlevi hesaplayan bir indirgeme, karar verilemeyen bir sorunu karar verilebilir bir soruna indirebilir . Michael Sipser'in Hesaplama Teorisine Giriş'te belirttiği gibi : "Sınıftaki tipik problemlerin karmaşıklığına göre indirgeme kolay olmalıdır [...] problem, ona indirgenen problemlere mutlaka kolay bir çözüm getirmez."

Bu nedenle, uygun indirgeme kavramı, çalışılan karmaşıklık sınıfına bağlıdır. NP karmaşıklık sınıfını ve polinom hiyerarşisi gibi daha zor sınıfları incelerken , polinom zaman azaltmaları kullanılır. NC ve NL gibi P içindeki sınıfları incelerken , log-alanı azaltmaları kullanılır. İndirgemeler, problemlerin makineler tarafından çözülüp çözülmediğini göstermek için hesaplanabilirlik teorisinde de kullanılır ; bu durumda, indirgemeler yalnızca hesaplanabilir işlevlerle sınırlıdır .

Optimizasyon (maksimizasyon veya minimizasyon) problemlerinde, genellikle yaklaşımı koruyan indirgeme açısından düşünürüz . İki optimizasyon problemimiz olduğunu varsayalım, öyle ki, bir problemin örnekleri diğerinin örnekleriyle eşleştirilsin, böylece ikinci problemin örneklerine neredeyse optimal çözümler, birincisine neredeyse optimal çözümler verecek şekilde geri dönüştürülebilir. Bu yolla, eğer B probleminin örneklerine en iyiye yakın (veya en uygun) çözümler bulan bir optimizasyon algoritmamız (veya yaklaşıklık algoritmamız ) ve A probleminden B problemine etkili bir yaklaşıklığı koruyan indirgememiz varsa, bir optimizasyon elde ederiz. A probleminin örneklerine en iyiye yakın çözümler veren algoritma. Yaklaşımı koruyan indirgemeler genellikle yaklaşıklık sonuçlarının sertliğini kanıtlamak için kullanılır : eğer bazı optimizasyon problemlerini (bazı karmaşıklık varsayımları altında) bazıları için α'dan daha iyi bir faktör dahilinde yaklaşık olarak tahmin etmek zorsa α, ve A probleminden B problemine β-yaklaşımını koruyan bir azalma var, B probleminin α/β faktörü içinde tahmin edilmesinin zor olduğu sonucuna varabiliriz.

Örnekler

Ayrıntılı örnek

Aşağıdaki örnek, bir dilin karar verilemez olduğunu kanıtlamak için durma probleminden indirgemenin nasıl kullanılacağını gösterir. Varsayalım ki H ( M , w ) belirli bir Turing makinesi M'nin w girdi dizgisinde (kabul ederek veya reddederek) durup durmadığını belirleme problemidir . Bu dilin kararsız olduğu bilinmektedir. E ( M ), verilen bir Turing makinesi M'nin kabul ettiği dilin boş olup olmadığını (başka bir deyişle, M'nin herhangi bir dizi kabul edip etmediğini ) belirleme problemi olduğunu varsayalım . H'den bir indirgeme ile E'nin kararsız olduğunu gösteriyoruz .

Bir çelişki elde etmek için, R'nin E için bir karar verici olduğunu varsayalım . Bunu, H için bir karar verici S üretmek için kullanacağız (ki bunun var olmadığını biliyoruz). Verilen giriş M ve W (Turing makinesi ve bir giriş dizesi) tanımlama, S ( M , W ), aşağıdaki davranış ile: S Turing makine oluşturur , N giriş dizesi yalnızca kabul N olduğu ağırlık ve M girişi durur ağırlık , ve başka türlü durmaz. Final S hemen değerlendirebilir R ( K ) kabul dil olmadığını kontrol etmek için N boştur. Eğer R, kabul N , o zaman kabul dil N , özellikle çok boş, M girişi durdurmak etmez ağırlık , yani S reddedebilir. Eğer R, reddeder N , o zaman kabul dil N , böylece boş olmayan bir E girişi durdurmak yapar ağırlık , yani S kabul edebilir. Böylece, E için bir karar vericimiz R olsaydı , herhangi bir makine M ve girdi w için H ( M , w ) durma problemi için bir karar verici S üretebilirdik . Böyle bir S'nin olamayacağını bildiğimize göre , E dilinin de karar verilemez olduğu sonucu çıkar.

Ayrıca bakınız

Referanslar

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest ve Clifford Stein, Algoritmalara Giriş, MIT Press, 2001, ISBN  978-0-262-03293-3
  • Hartley Rogers, Jr.: Özyinelemeli Fonksiyonlar ve Etkili Hesaplanabilirlik Teorisi, McGraw-Hill, 1967, ISBN  978-0-262-68052-3 .
  • Peter Bürgisser: Cebirsel Karmaşıklık Teorisinde Tamlık ve Azaltma, Springer, 2000, ISBN  978-3-540-66752-0 .
  • ER Griffor: Hesaplanabilirlik Teorisi El Kitabı, Kuzey Hollanda, 1999, ISBN  978-0-444-89882-1 .