Teoretyczne informatyka

1

Jak problem może występować w NP, być trudnym NP, a nie kompletnym NP?

Najdłużej myślałem, że problem był NP-zupełny, jeśli jest zarówno (1) NP-trudny, jak i (2) jest w NP. Jednak w słynnym artykule „Metoda elipsoidy i jej konsekwencje w optymalizacji kombinatorycznej” autorzy twierdzą, że problem ułamkowej liczby chromatycznej należy do NP i jest trudny do NP, ale nie jest znany jako NP-zupełny. …

14 cc.complexity-theory np-hardness complexity-classes terminology

1

Zbliżenie przestrzeni Kompromis

W swojej pracy odległości około Oracles , Thorup i Zwick wykazały, że dla każdego wykresu ważonej nieukierunkowane, możliwe jest skonstruowanie struktury danych o rozmiarze , które mogą powrócić do -approximate odległość między dowolną parą wierzchołków na wykresie.O ( k n1 + 1 / k)O(kn1+1/k)O(k n^{1+1/k})( 2 k - 1 )(2)k-1)(2k-1) …

14 ds.algorithms graph-theory approximation-algorithms space-complexity

1

Najlepsza złożoność komunikacji dolna granica rozłączności

Dobrze wiadomo, że żaden deterministyczny protokół dwupartyjny nie może rozwiązać problemu rozłączności (DISJ) na wejściach bitowych bez wysyłania n + 1 bitów w najgorszym przypadku (patrz np. Książka Kushilevitza i Nisana). W przypadku protokołów losowych z ograniczonym błędem dolną granicę δ n , dla niektórych stałych δ , pokazano również …

14 lower-bounds communication-complexity

1

Obliczanie elipsoidy wielościanu Löwnera-Johna

Elipsoida Löwnera-Johna z wypukłego zestawu jest elipsoidą o minimalnej objętości (MVE), która ją otacza. Elipsoidę można obliczyć metodą Khachiyana i istnieje wiele przybliżeń, jeśli C jest (wypukłym kadłubem) zbiorem punktów.dodoCdodoC Czy istnieją szybkie (tj. Oparte na metodzie nieelipsoidalnej) aproksymacje MVE ograniczonego wielościanu przedstawione tylko w odniesieniu do półpłaszczyzn, których przecięcia …

14 cg.comp-geom convex-geometry

2

Najmniejszy zestaw nie zawarty w kolekcji zestawów

Ze względu na wejściu liczba całkowita nnn i zestaw SSS zestawów elementów {1,...,n}{1,...,n}\{1, ..., n\} , co jest złożoność znalezienia zestawu TTT z elementami {1,...,n}{1,...,n}\{1, ..., n\} takie, że TTT ma minimalną liczność, a TTT jest zawarty w żadnym zestawie SSS ?

14 cc.complexity-theory ds.algorithms

1

Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu?

W artykule Randomized Primal-Dual analiza RANKING dla Online Dwustronnego dopasowywania , udowadniając jednocześnie, że algorytm RANKING jest -konkurencyjne, autorzy pokazują, że dualność jest wykonalna w oczekiwaniu (patrz Lemat 3 na stronie 5). Moje pytanie brzmi:(1−1e)(1−1e)\left(1 - \frac{1}{e}\right) Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu? Jedną rzeczą jest …

14 linear-programming randomized-algorithms online-algorithms matching primal-dual

3

Wymiana prezentów od białego słonia: mechanizmy sprawiedliwego podziału

Popularną grą na wakacyjnych imprezach w Ameryce Północnej jest wymiana prezentów z białym słoniem . W skrócie (ignorowanie odmian) działa to w następujący sposób: Jest ludzi i n zapakowanych prezentów. Gracze są sortowani arbitralnie. W í th okrągłym, odtwarzacz i albonnnnnnjathjathi^{\text{th}}jajai wybiera zapakowany prezent i rozpakowuje go jako prezent „kradnie” …

14 gt.game-theory mechanism-design

1

η-konwersja vs rozciągliwość w rozszerzeniach rachunku lambda

Często myli mnie związek między konwersją η a ekstensywnością. Edytuj: Według komentarzy wydaje mi się, że jestem również zdezorientowany co do związku między równoważnością ekstensywną a równoważnością obserwacyjną. Ale przynajmniej w Agdzie z ekstensywną równością funkcji (jako postulat) i dla prostego rachunku lambda (który ma w pełni abstrakcyjną semantykę, jeśli …

14 pl.programming-languages lambda-calculus

1

Klasa złożoności związana z wyczerpującym wyszukiwaniem

Jaka klasa złożoności jest powiązana z wyczerpującymi algorytmami wyszukiwania? (jeśli jest) Czy to jest NP czy PSPACE? Czy istnieją ograniczone modele obliczeń przechwytujące klasę wyczerpujących algorytmów wyszukiwania podobnych do modeli dla chciwego i dynamicznego programowania?

14 cc.complexity-theory ds.algorithms reference-request big-picture machine-models

2

0-1 Programowanie liniowe: obliczanie optymalnej formuły

Rozważmy nnn -wymiarowej przestrzeni {0,1}n{0,1}n\{0,1\}^n , niech ccc być liniowy ograniczenie formy 1 x 1 + 2 x 2 + 3 x 3 + . . . + a n - 1 x n - 1 + a n x n ≥ k , gdzie a i ∈ R , …

14 reference-request co.combinatorics optimization linear-programming convex-optimization

2

Podejścia do GI inspirowane problemem węzłów

Zarówno GI, jak i Knot Problem stanowią problem decydowania o równoważności strukturalnej obiektów matematycznych. Czy są jakieś wyniki ustanawiające powiązania między nimi? Ładne powiązania problemu węzłów z fizyką statystyczną zostały zbadane za pomocą wielomianów węzłów , czy istnieją podobne wyniki dla ?G IsoljaGI Byłoby to szczególnie pomocne, aby wiedzieć, czy …

14 cc.complexity-theory reference-request graph-theory graph-isomorphism algebraic-topology

3

Znaczenie złożoności stanu w automatach i językach regularnych?

Czytam „ Łączenie zwykłych języków i złożoności opisowej ” Galiny Jiraskowej z 2009 r. Na temat złożoności państwa wynikającej z połączenia dwóch zwykłych języków (Galiny Jiraskowej), ale nie rozumiem, jakie byłyby praktyczne implikacje złożoności państwa . Pierwszą trywialną myślą, która mnie uderzyła, było to, że większa złożoność wymagałaby więcej czasu …

14 fl.formal-languages automata-theory regular-language

2

Parametr wykresu prawdopodobnie związany z szerokością

Interesują mnie wykresy nnn wierzchołków, które można wytworzyć w następujący sposób. Zacznij od dowolnego wykresu GsolG na k≤nk≤nk\le n wierzchołków. Oznacz wszystkie wierzchołki w GsolG jako nieużywane . Opracowanie nowego wykres dodaje się nowy wierzchołek V , który jest połączony z jedną lub więcej niewykorzystanych wierzchołków G i nie jest …

14 ds.algorithms graph-theory treewidth

1

Przyspieszenie dzięki postępom algorytmicznym w porównaniu ze sprzętem

Pamiętam jakiś czas temu badanie lub artykuł, w którym twierdziłem, że większość przyspieszenia obserwowanego w programach komputerowych w ciągu ostatnich kilku dekad wynika z lepszych algorytmów niż z szybszego sprzętu. Czy ktoś zna badanie lub artykuł?

14 ds.algorithms reference-request big-picture ar.hardware-architecture

1

Czy można udowodnić za pomocą twierdzenia Linial-Mansour-Nisan i znajomości czteroczęściowego spektrum ?

Wynik 1: Twierdzenie Linial-Mansour-Nisan mówi, że czteroliniowa waga funkcji obliczonych przez obwody jest skoncentrowana na podzbiorach małych rozmiarów z dużym prawdopodobieństwem.AC0AC0\mathsf{AC}^0 Wynik 2: ma czterokierunkową wagę skoncentrowaną na współczynniku stopnia .PARITYPARITY\mathsf{PARITY}nnn Pytanie: Czy istnieje sposób, aby udowodnić (jeśli można udowodnić), że nie jest obliczalny przez obwody przez / przy użyciu …

14 cc.complexity-theory circuit-complexity boolean-functions fourier-analysis