Journal of the European Mathematical Society· 2026Q1
Moser–Tardos Algoritması az sayıda rastgele bit ile
Moser–Tardos Algorithm with small number of random bits
- 2atıf
- Q1SCImago
- 2026yıl
Kısa özet
Paralel Moser–Tardos Algoritması'nın bir varyantı, alt-üstel bağımlılık grafiği büyümesine sahip problemler için sabit, değişkenden bağımsız sayıda rastgele bit kullanır ve O(n) deterministik çalışma süresi elde eder.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- Paralel Moser–Tardos Algoritması'nın bir varyantı, alt-üstel bağımlılık grafiği büyümesine sahip problemler için sabit sayıda rastgele bit kullanır.
- Rastgele bitler, bağımlılık grafiğinde birbirinden uzak değişkenler için yeniden kullanılır.
- Bu, tatmin edici atamaları bulmak için O(n) çalışma süresine sahip deterministik bir algoritma ile sonuçlanır.
- Lovász Yerel Lemması'nın bir Borel versiyonu da sunulmaktadır.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
We study a variant of the parallel Moser–Tardos Algorithm. We prove that if we restrict attention to a class of problems whose dependency graphs have subexponential growth, then the expected total number of random bits used by the algorithm is constant; in particular, it is independent of the number of variables. This is achieved by using the same random bits to resample variables which are far enough in the dependency graph. There are two corollaries. First, we obtain a deterministic algorithm for finding a satisfying assignment, which for any class of problems as in the previous paragraph runs in time O(n) , where n is the number of variables. Second, we present a Borel version of the Lovász Local Lemma.
Yazarların özeti; kaynağından alınmıştır. Journal of the European Mathematical Society, 2026 · DOI ↗
Ücretsiz hesapla devam et
Makaleye Sor ile bu makaleye günde 3 soru ücretsiz; makaleyi kaydet, kaynakçasını al, ilgi alanına göre her gün yeni özetler. Çıkarımlar Premium.
Web'de ücretsiz devam etGoogle ya da Apple hesabınla giriş; kart istemez. Bu makaleye geri dönersin.
Telefonda:
Alan: Matematiksel Fizik
Mathematical PhysicsMathematics