Matroid oracle - Matroid oracle

Matematik ve bilgisayar bilimlerinde bir matroid oracle bir altyordam içinden algoritma erişebilir matroid açıklamak için kullanılabilecek soyut bir kombinatoryal yapı doğrusal bağımlılıklar bir içindeki vektörler arasında vektör alanı ya da ağaçları kapsayan bir grafik, diğer uygulamalar arasında.

Bu türden en yaygın olarak kullanılan oracle, bir matroid elemanlarının bağımsız olup olmadığını test etmek için bir alt program olan bir bağımsızlık oracle'dır. Birkaç başka kehanet türü de kullanılmıştır; bazılarının bağımsızlık kahinlerinden daha zayıf, bazılarının daha güçlü ve bazılarının hesaplama gücünde eşdeğer olduğu gösterilmiştir.^[1]

Birçok algoritmalar Matroidler üzerinde hesaplamalar yapan, bir oracle'ı girdi olarak alacak şekilde tasarlandı ve birçok farklı matroid üzerinde değişiklik yapmadan ve ne tür bir matroid kullandıklarına dair ek varsayımlar olmadan verimli bir şekilde çalışmasına izin verdi. Örneğin, herhangi bir matroid için bir bağımsızlık oracle'ı verildiğinde, matroidin minimum ağırlık tabanını bir uygulayarak bulmak mümkündür. Açgözlü algoritma Bu, her bir öğenin eklenip eklenemeyeceğini test etmek için bağımsızlık oracle'ını kullanarak, ağırlığa göre sıralanmış olarak temele öğeler ekler.^[2]

İçinde hesaplama karmaşıklığı teorisi, oracle modeli koşulsuz yol açtı alt sınırlar Bazı matroid problemlerinin polinom zamanında çözülemeyeceğini kanıtlamak, varsayım gibi kanıtlanmamış varsayımlara başvurmadan P ≠ NP. Bu şekilde zor olduğu gösterilen sorunlar, bir matroid olup olmadığını test etmeyi içerir. ikili veya üniforma veya belirli sabitleri içerip içermediğini test etmek küçükler.^[3]

Neden kahinler?

Bazı yazarlar matroidlerin tüm bağımsız kümelerini veya matroidin tüm temel kümelerini açıkça listeleyen bilgisayar temsillerini denemiş olsalar da,^[4] bu temsiller değil kısa ve öz: bir matroid ${ displaystyle scriptstyle n}$ elemanlar, üstel olarak alan alan bir gösterime genişleyebilir. ${ displaystyle scriptstyle n}$. Aslında, üzerinde farklı matroidlerin sayısı ${ displaystyle scriptstyle n}$ elemanlar büyür katlanarak iki katına gibi

${ displaystyle 2 ^ {2 ^ {n} n ^ {- 3/2 + o (1)}}}$^[5]

bundan, tüm olası matroidleri idare edebilen herhangi bir açık temsilin zorunlu olarak üstel uzay kullanacağı sonucu çıkar.^[6]

Bunun yerine, farklı matroid türleri, tanımlandıkları diğer yapılardan daha verimli bir şekilde temsil edilebilir: tek tip matroidler iki sayısal parametresinden, grafik matroidler, iki dairesel matroidler, ve gammoids grafiklerden doğrusal matroidler itibaren matrisler, vb. Ancak, rasgele matroidler üzerinde hesaplamalar yapmak için bir algoritma, bu matroid sınıflarının her biri için yeniden tasarlanmak yerine, argümanına erişmek için tek tip bir yönteme ihtiyaç duyar. Oracle modeli, bir algoritmanın ihtiyaç duyabileceği erişim türlerini kodlamak ve sınıflandırmak için uygun bir yol sağlar.

Tarih

İle başlayan Rado (1942), "bağımsızlık işlevleri" veya "${ displaystyle scriptstyle I}$-fonksiyonlar "matroidleri aksiyomatize etmenin birçok eşdeğer yolundan biri olarak incelenmiştir. Bir bağımsızlık fonksiyonu, bir dizi matroid öğesini sayıya eşler ${ displaystyle scriptstyle 1}$ küme bağımsız ise veya ${ displaystyle scriptstyle 0}$ bağımlı ise; yani, bu gösterge işlevi bağımsız kümeler ailesinin, özünde bir bağımsızlık kahini ile aynı şey.^[7]

Matroid oracles, matroidler üzerindeki en eski algoritmik çalışmanın bir parçası olmuştur. Böylece, Edmonds (1965), matroid bölme problemlerini incelerken, verilen matroide erişimin girdi olarak bağımsız bir küme alan bir alt yordam yoluyla olduğunu varsaydı. ${ displaystyle scriptstyle I}$ ve bir element ${ displaystyle scriptstyle x}$veya içinde bir devre döndürür ${ displaystyle scriptstyle I cup {x }}$ (zorunlu olarak benzersiz ve içeren ${ displaystyle scriptstyle x}$, eğer varsa) veya böyle bir devrenin olmadığını belirler. Edmonds (1971) belirli bir kümenin bağımsız olup olmadığını (yani daha modern terminolojide bir bağımsızlık kahini) test eden bir alt yordam kullandı ve sağladığı bilgilerin polinom zamanda minimum ağırlık temelini bulmak için yeterli olduğunu gözlemledi.

İşinden başlayarak Korte ve Hausmann (1978) veHausmann ve Korte (1978) araştırmacılar, matroidler ve ilgili yapılar için algoritmalar üzerinde daha düşük sınırları kanıtlama bakış açısından oracle'ları incelemeye başladı. Hausmann ve Korte tarafından yazılan bu iki makalenin her ikisi de, matroidler için kolay olan, ancak (gösterdikleri gibi) tam olarak yaklaşması veya daha genel olarak hesaplaması daha zor olan maksimum kardinalite bağımsız bir küme bulma sorunuyla ilgiliydi. bağımsızlık sistemleri bağımsızlık kahini ile temsil edilir. Bu çalışma, 1970'lerin sonlarında ve 1980'lerin başlarında matroidlerdeki problemler için benzer sertlik sonuçları gösteren bir kağıt telaşı başlattı.^[8] ve farklı türdeki matroid oracle'larının gücünü karşılaştırmak.^[9]

O zamandan beri, bağımsızlık kahini matroid algoritmalarıyla ilgili çoğu araştırma için standart hale geldi.^[10] Alt sınırlarla ilgili araştırmalar da devam ediyor,^[11] ve farklı kehanet türlerinin karşılaştırmaları.^[12]

Oracle türleri

Aşağıdaki matroid oracle türleri dikkate alınmıştır.

• Bir bağımsızlık kahini girdi olarak bir dizi matroid eleman alır ve çıktı olarak a Boole değeri, verilen küme bağımsızsa true, aksi takdirde false.^[13] Matroidin tanımlandığı temel yapıya dayalı olarak kolayca uygulanabilir. grafik matroidler, enine matroidler, gammoids ve doğrusal matroidler ve bunlardan doğrudan toplamlar gibi standart işlemlerle oluşturulan matroidler için.^[3]
• Kahin Edmonds (1965) girdi olarak bağımsız bir küme ve ek bir öğe alır ve bunların birleşiminin bağımsız olduğunu belirler veya birleşimde bir devre bulur ve onu döndürür.
• Bir rütbe oracle girdi olarak bir dizi matroid eleman alır ve çıktısı olarak sayısal bir değer döndürür. sıra verilen setin.^[9]
• Bir temel oracle girdi olarak bir dizi matroid öğesi alır ve çıktı olarak bir Boolean değeri döndürür; verilen küme bir temelse true, aksi takdirde false.^[9]
• Bir çevre oracle girdi olarak bir matroid elemanlar kümesini alır ve çıktı olarak bir Boolean değeri döndürür; verilen küme bir devre ise true, aksi takdirde false.^[9]
• Üç tür kapanış kahini Belirli bir elemanın belirli bir setin kapanışına ait olup olmadığını test eden, setin kapanışını döndüren ikincisi ve belirli bir setin kapanıp kapanmadığını test eden üçüncüsü.^[9]
• Bir kehanet girdi olarak bir dizi matroid elemanını alır ve çıktı olarak bir Boolean değeri döndürür, eğer verilen küme yayılıyorsa (yani bir temel içeriyorsa ve tüm matroid ile aynı sıraya sahipse), aksi takdirde yanlış.^[14]
• Bir çevresi oracle girdi olarak bir dizi matroid eleman alır ve çıktısı olarak sayısal bir değer, bu kümedeki en küçük devrenin boyutunu (veya ${ displaystyle scriptstyle + infty}$ verilen küme bağımsız ise).^[14]
• Bir liman oracle sabit bir eleman için ${ displaystyle scriptstyle x}$ Matroid, girdisi olarak bir dizi matroid eleman alır ve çıktı olarak bir Boolean değeri döndürür, eğer verilen küme aşağıdakileri içeren bir devre içeriyorsa doğru ${ displaystyle scriptstyle x}$ aksi takdirde yanlış.^[15]

Farklı kahinlerin göreceli gücü

Bilinen birçok kehanet türü olmasına rağmen, bunların birçoğu hesaplama gücünde eşdeğer olduğundan hangisinin kullanılacağının seçimi basitleştirilebilir. Bir kehanet ${ displaystyle scriptstyle X}$ olduğu söyleniyor polinomik olarak indirgenebilir başka bir kahine ${ displaystyle scriptstyle Y}$ herhangi bir çağrı varsa ${ displaystyle scriptstyle X}$ sadece oracle kullanarak matroide erişen bir algoritma tarafından simüle edilebilir ${ displaystyle scriptstyle Y}$ ve alır polinom zamanı matroidin elemanlarının sayısı cinsinden ölçüldüğü gibi; karmaşıklık-teorik terimlerle, bu bir Turing azaltma. İki kahin olduğu söyleniyor polinomiye eşdeğer birbirlerine polinomik olarak indirgenebilirlerse. Eğer ${ displaystyle scriptstyle X}$ ve ${ displaystyle scriptstyle Y}$ polinomik olarak eşdeğerdir, bu durumda oracle kullanan bir matroid problemi için bir polinom zaman algoritmasının varlığını veya yokluğunu kanıtlayan her sonuç ${ displaystyle scriptstyle X}$ aynı şeyi oracle için de kanıtlıyor ${ displaystyle scriptstyle Y}$.

Örneğin, bağımsızlık kehanı, polinomik olarak şunun devre bulma kahinine eşdeğerdir. Edmonds (1965). Bir devre bulma oracle mevcutsa, bir set bağımsızlık için en fazla test edilebilir. ${ displaystyle scriptstyle n}$ bir boş küme, verilen setin öğelerini her seferinde bir öğe eklemek ve devre bulma oracle'ını kullanarak her bir eklemenin şimdiye kadar inşa edilmiş olan setin bağımsızlığını koruyup korumadığını test etmek. Diğer yönde, bir bağımsızlık kahini varsa, bir setteki devre ${ displaystyle scriptstyle I cup {x }}$ en çok kullanılarak bulunabilir ${ displaystyle scriptstyle n}$ her element için test ederek oracle'a çağrılar ${ displaystyle scriptstyle y I’de}$, eğer ${ displaystyle scriptstyle I setminus {y } cup {x }}$ bağımsızdır ve cevabın hayır olduğu unsurları döndürür. Bağımsızlık kahini aynı zamanda rütbe kahinine, yayılan oracle'a, ilk iki tür kapatma oracle'ına ve port oracle'a polinomik olarak eşdeğerdir.^[1]

Temel oracle, devre oracle ve belirli bir setin kapalı olup olmadığını test eden oracle, bağımsızlık oracle'ından daha zayıftır: Bir bağımsızlık oracle'ı kullanarak matroide erişen bir algoritma tarafından polinom zamanında simüle edilebilirler, ancak tersi olamaz. . Ek olarak, bu üç oracle'ın hiçbiri polinom zamanı içinde birbirini simüle edemez. Çevresi kehaneti aynı anlamda bağımsızlık kehanetinden daha güçlüdür.^[9]

Polinom zaman Turing azaltımlarının yanı sıra, diğer indirgenebilirlik türleri de dikkate alınmıştır. Özellikle, Karp, Upfal ve Wigderson (1988) gösterdi ki paralel algoritmalar rütbe ve bağımsızlık oracle'ları hesaplama gücü açısından önemli ölçüde farklıdır. Rütbe kahini, asgari ağırlık temelinin inşasına izin verir. ${ displaystyle scriptstyle n}$ matroid öğelerinin sıralı sırasının öneklerinin eşzamanlı sorguları: bir öğe, ancak ve ancak önekinin sıralaması önceki önekin düzeyinden farklıysa optimum temele aittir. Aksine, bir bağımsızlık kehaneti ile asgari bir temel bulmak çok daha yavaştır: belirleyici olarak şu şekilde çözülebilir: ${ displaystyle scriptstyle O ({ sqrt {n}})}$ zaman adımları ve daha düşük bir sınır vardır ${ displaystyle scriptstyle Omega ((n / log n) ^ {1/3})}$ rastgele paralel algoritmalar için bile.

Algoritmalar

Matroidlerdeki birçok problemin çözülebildiği bilinmektedir. polinom zamanı, matroid'e yalnızca bir bağımsızlık kahini veya eşdeğer güce sahip başka bir oracle aracılığıyla erişen algoritmalarla, onlara ne tür bir matroid verildiğine dair herhangi bir ek varsayıma ihtiyaç duymadan. Bu polinomik olarak çözülebilir sorunlar şunları içerir:

• Bir minimum veya maksimum ağırlık esasını bulmak ağırlıklı matroid, kullanarak Açgözlü algoritma.^[2]
• Bir matroidin elemanlarını minimum sayıda bağımsız kümeye ayırmak ve verilen iki matroid içinde aynı anda bağımsız olan en büyük kümeyi bulmak. İkinci soruna denir matroid kesişimi ve her iki sorunun çözümleri de birbiriyle yakından ilişkilidir.^[16]
• Bir matroid olup olmadığını test etmek ${ displaystyle scriptstyle k}$bağlantılı (anlamında Tutte 1966 ) için ${ displaystyle scriptstyle k leq 3}$.^[17]
• Belirli bir matroid olup olmadığını test etme grafik^[18] veya düzenli.^[19]
• Bir kulak çürümesi belirli bir matroidin, birliği matroid olan ve dizideki önceki tüm devreler kısaltıldıktan sonra her devrenin bir devre olarak kaldığı bir dizi devre. Böyle bir ayrıştırma, seçilen bir matroid elemanının her devreye ait olduğu ek özelliğiyle de bulunabilir.^[15]
• Bir dal ayrışması dal genişliği sabit bir sabitten fazla olmadığı zaman, belirli bir matroid için.^[20]
• Bir matroidin tüm tabanlarını, dairelerini veya devrelerini çıktı kümesi başına polinom zamanı cinsinden listeleme.^[21]
• Baz sayısını a ile yaklaşık tamamen polinom zamanlı randomize yaklaşım şeması bir matroid için ${ displaystyle scriptstyle n}$ öğeler ve rütbe ${ displaystyle scriptstyle r}$baz sayısının, sayısının polinom faktörü dahilinde olduğu ek varsayımıyla ${ displaystyle scriptstyle r}$-element setleri.^[22]

İmkansızlık kanıtları

Birçok matroid problemi için, bir bağımsızlık kahininin, problemin polinom zamanında çözülmesine izin verecek kadar yeterli gücü sağlamadığını göstermek mümkündür. Bu ispatların ana fikri iki matroid bulmaktır. ${ displaystyle scriptstyle M}$ ve ${ displaystyle scriptstyle M '}$ Hangi sorunun cevabının farklı olduğu ve hangilerinin bir algoritmanın ayırt etmesi zor. Özellikle, eğer ${ displaystyle scriptstyle M}$ yüksek derecede simetriye sahiptir ve ${ displaystyle scriptstyle M '}$ yalnızca az sayıda sorguya verilen yanıtlarda, bir algoritmanın bir tür girdiyi ayırt ettiğinden emin olması için çok fazla sayıda sorgu gerekebilir ${ displaystyle scriptstyle M}$ simetrilerinden biri kullanılarak oluşturulan bir girdiden ${ displaystyle scriptstyle M}$ izin vermek ${ displaystyle scriptstyle M '}$.^[3]

Bu yaklaşımın basit bir örneği, bir matroidin olup olmadığını test etmenin zor olduğunu göstermek için kullanılabilir. üniforma. Gösterim kolaylığı için, izin verin ${ displaystyle scriptstyle n}$ eşit ol, bırak ${ displaystyle scriptstyle M}$ tek tip matroid ol ${ displaystyle scriptstyle U {} _ {n} ^ {n / 2}}$ve izin ver ${ displaystyle scriptstyle M '}$ bir matroid olmak ${ displaystyle scriptstyle M}$ tek bir tane yaparak ${ displaystyle scriptstyle n / 2}$-element temel setleri ${ displaystyle scriptstyle M}$ bağımsız yerine bağımlı. Bir algoritmanın girdisinin tek tip olup olmadığını doğru bir şekilde test etmesi için, ayırt edebilmesi gerekir. ${ displaystyle scriptstyle M}$ olası her permütasyonundan ${ displaystyle scriptstyle M '}$. Ancak deterministik bir algoritmanın bunu yapması için, her birini test etmesi gerekir. ${ displaystyle scriptstyle n / 2}$Elemanların eleman altkümeleri: Bir seti kaçırırsa, bağımlı yapmak için aynı seti seçen bir kahin tarafından kandırılabilir. Bu nedenle, bir matroidin tek tip olup olmadığının test edilmesi gerekebilir

${ displaystyle { binom {n} {n / 2}} = Omega sol ({ frac {2 ^ {n}} { sqrt {n}}} sağ)}$

bağımsızlık sorguları, polinomdan çok daha yüksek. Rastgele bir algoritma bile, bu iki matroidi ayırt etmekten emin olmak için neredeyse aynı sayıda sorgu yapmalıdır.^[23]

Jensen ve Korte (1982) Bu yaklaşımı, iki matroid var olduğunda kanıtlayarak resmileştirin ${ displaystyle scriptstyle M}$ ve ${ displaystyle scriptstyle M '}$ aynı öğe kümesinde, ancak farklı problem cevaplarıyla, bu öğeler üzerinde verilen sorunu doğru bir şekilde çözen bir algoritma en azından kullanmalıdır

${ displaystyle { frac {| operatöradı {aut} (M) |} { toplamı _ {i} | operatöradı {düzeltme} (M, Q_ {i}) |}}}$

sorgular, nerede ${ displaystyle scriptstyle operatöradı {aut} (M)}$ gösterir otomorfizm grubu nın-nin ${ displaystyle scriptstyle M}$, ${ displaystyle scriptstyle Q_ {i}}$ bağımsızlığı farklı olan kümeler ailesini belirtir ${ displaystyle scriptstyle M}$ -e ${ displaystyle scriptstyle M '}$, ve ${ displaystyle scriptstyle operatöradı {düzeltme} (M, Q_ {i})}$ eşleme yapan otomorfizmlerin alt grubunu belirtir ${ displaystyle scriptstyle Q_ {i}}$ kendisine. Örneğin, tek tip matroidin otomorfizm grubu sadece simetrik grup, boyutla ${ displaystyle scriptstyle n!}$ve tek tip matroidleri test etme probleminde sadece bir set vardı ${ displaystyle scriptstyle Q_ {i}}$ ile ${ displaystyle scriptstyle | operatöradı {düzeltme} (M, Q_ {i}) | = (n / 2)! ^ {2}}$, üstel bir faktör kadar küçüktür ${ displaystyle scriptstyle n!}$.^[24]

Bir matroid oracle algoritmasının polinom zamanında hesaplamasının imkansız olduğu kanıtlanan sorunlar şunları içerir:

• Belirli bir matroidin tek tip olup olmadığını test etmek.^[23]
• Belirli bir matroidin sabit bir matroid içerip içermediğini test etme ${ displaystyle scriptstyle H}$ küçük olarak, özel durumlar dışında ${ displaystyle scriptstyle H}$ en fazla bir rütbe veya corank ile tek tiptir. Daha genel olarak, eğer ${ displaystyle scriptstyle { mathcal {H}}}$ sabit sonlu bir matroid kümesidir ve tek tip matroid yoktur ${ displaystyle scriptstyle { mathcal {H}}}$, bu durumda polinom zamanında belirli bir matroidin bir veya daha fazla matroid içerip içermediğini test etmek mümkün değildir. ${ displaystyle scriptstyle { mathcal {H}}}$ küçük olarak.^[25]
• Belirli bir matroid olup olmadığını test etme ikili, herhangi bir belirli sabit üzerinde gösterilebilir alan veya üzerinde gösterilebilir olduğu bir alan olup olmadığı.^[26]
• Girişin bir grafik ve köşelerinde bir matroid olduğu ve amacın bir matroid eşleme problemini çözme eşleştirme mümkün olduğunca büyük olan grafikte, eşleşen köşelerin bağımsız bir küme oluşturması kısıtlamasına tabidir.^[27]
• Belirli bir matroid olup olmadığını test etme öz-ikili, enine, iki parçalı, Euler veya yönlendirilebilir.^[3]
• Çevrenin hesaplanması (en küçük devrenin boyutu), en büyük devrenin boyutu, devre sayısı, üs sayısı, daire sayısı, maksimum sıra daire sayısı, en büyük dairenin boyutu, Tutte polinomu veya belirli bir matroidin bağlantısı.^[3]

Tüm özellikler kümesi arasında ${ displaystyle scriptstyle n}$-element matroidleri, test etmek için üstel zaman gerektirmeyen özelliklerin kesri, sınırda sıfıra gider. ${ displaystyle scriptstyle n}$ sonsuza gider.^[6]

Ayrıca bakınız

• Kara kutu grubu için oracle benzeri bir model grup teorisi
• Örtük grafik, grafik algoritmaları için oracle benzeri bir model

Notlar

Referanslar