Pytania otagowane jako counting-complexity

Jak trudno policzyć liczbę rozwiązań?

1
Redukcja przestrzeni logów z obwodów Parity-L na obwody CNOT?
Pytanie. W swoim artykule Ulepszona symulacja obwodów stabilizatora , Aaronson i Gottesman twierdzą, że symulacja obwodu CNOT jest zakończona w ⊕L (przy zmniejszeniu przestrzeni logarytmicznej). Oczywiste jest, że jest on zawarty w ⊕L ; jak zachowuje się wynik twardości? Równoważnie: czy występuje ograniczenie przestrzeni logicznej z iterowanych produktów macierzy modulo …
3
Jak mogę pokazać, że problem Gap-P jest poza #P
Istnieje wiele problemów w kombinatorycznej teorii reprezentacji i geometrii algebraicznej, dla których nie jest znana formuła dodatnia. Myślę o kilku przykładach, ale pozwólcie, że obliczę współczynniki Kroneckera jako mój przykład. Zwykle pojęcie „formuły dodatniej” nie jest precyzyjnie zdefiniowane w kombinatorykach, ale z grubsza oznacza „opis jako liczność zbioru rozsądnie wyraźnego”. …
4
Zliczanie liczby osłon wierzchołków: kiedy jest to trudne?
Rozważmy problem # P-zupełny liczenia liczby osłon wierzchołków danego wykresu G=(V,E)G=(V,E)G = (V, E) . Chciałbym wiedzieć, czy jest jakikolwiek wynik pokazujący, jak twardość takiego problemu zmienia się w zależności od parametru (na przykład ).GGGd=|E||V|d=|E||V|d = \frac{|E|}{|V|} Mam wrażenie, że problem powinien być łatwiejszy zarówno wtedy, gdy jest rzadki, jak …
3
Złożoność sprawdzania, czy dwa CNF mają taką samą liczbę rozwiązań
Biorąc pod uwagę dwa CNF, jeśli mają taką samą liczbę zadań, aby były prawdziwe, odpowiedz „Tak”, w przeciwnym razie odpowiedz „Nie”. Łatwo zauważyć, że jest to w , ponieważ jeśli znamy dokładną liczbę rozwiązań dla tych dwóch CNF, po prostu je kampanujemy i odpowiadamy „Tak” lub „Nie”.P#PP#PP^{\#P} Jaka jest złożoność …
1
Parzystość-L vs. NL
Parzystość-L, znana również jako , jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko liczbę parzystą lub nieparzystą liczby ścieżek „akceptacji”. Ostatnie powiązane pytanie zadał Niel de Beaudrap.⊕⊕\oplus Moje pytanie jest następujące: Czy wiemy, czy NL ⊕ L? Czy te dwie klasy są uważane za nieporównywalne?⊆⊆\subseteq ⊕⊕\oplus
1
Czy liczenie maksymalnych klików na wykresie nieporównywalności # P jest kompletne?
To pytanie jest motywowane pytaniem MathOverflow Peng Zhanga . Valiant wykazał, że zliczanie maksymalnych klików na wykresie ogólnym jest zakończone metodą # P, ale co jeśli ograniczymy się do wykresów nieporównywalności (tzn. Chcemy policzyć maksymalne antichains w skończonym zestawie)? To pytanie wydaje się na tyle naturalne, że podejrzewam, że zostało …
4
Odnośnie do metod Pfaffa w liczeniu i kombinatoryce
Ostatnio zastanawiałem się nad wprowadzeniem do algorytmów holograficznych. Natknąłem się na obiekty kombinatoryczne zwane Pfaffians. W tej chwili tak naprawdę niewiele o nich wiem i natknąłem się na zaskakujące zastosowania, które można zastosować. Na przykład dowiedziałem się, że można ich używać do skutecznego liczenia liczby idealnych dopasowań na wykresach płaskich. …
2
Zliczanie roztworów wzorów Monotone-2CNF
Formuła Monotone-2CNF to formuła CNF, w której każda klauzula składa się z dokładnie 2 literałów dodatnich. Teraz mam wzór Monotone-2CNF . Niech S będzie zbiorem satysfakcjonujących zadań F. Mam również wyrocznię O, która może podać następujące informacje:FFFSSSFFFOOO Kardynalność zbioru (tj. Liczba rozwiązań F ).SSSFFF Biorąc pod uwagę zmienną : xxx …
2
Złożoność zliczania wszystkich połączonych podgrafów
Niech G będzie połączonym wykresem. Jaka jest złożoność zliczania wszystkich połączonych podgrafów, jeśli G jest następujących typów? G jest ogólny. G jest planarne. G jest dwustronny. Nie dbam o żadne struktury lub ..., po prostu muszę policzyć wszystkie połączone podgrupy! Interesuje mnie również złożoność zliczania wszystkich połączonych podsgrafów z dokładnie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.