Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Dolne granice niedeterministycznej komunikacji wielostronnej
Jest to kontynuacja mojego poprzedniego pytania dotyczącego dolnych granic komunikacji dla częściowych funkcji boolowskich . Czy ktoś może zasugerować jakieś odniesienie do dolnych granic niedeterministycznej komunikacji wielopartyjnej? Przeglądam dokumenty w terenie, ale wydaje się, że wszyscy wykazują separacje następującego typu: dolna granica dla protokołu losowego i (mniejsza) górna granica dla …
2
Twardość separatorów wierzchołków
Dla danego wykresu problem separatora pyta, czy istnieje zbiór wierzchołków lub krawędzi o małej liczności (lub wadze), którego usunięcie dzieli G na dwa rozłączne wykresy o w przybliżeniu równych rozmiarach. Nazywa się to problemem separatora wierzchołków, gdy usunięty zestaw jest zestawem wierzchołków, a problemem separatora krawędzi, gdy jest zestawem krawędzi. …
1
Czy ludzie patrzą na zagęszczenie pętli w obwodach boolowskich?
Podczas studiów licencjackich EE uczestniczyłem w kilku wykładach, które przedstawiały ładną charakterystykę obwodów boolowskich pod względem liczby zagnieżdżonych pętli. Ze złożonością obwody boolowskie są często uważane za sztylety, ale w rzeczywistości cykle sprzętowe są powszechne. Teraz, modulo kilka szczegółów technicznych dotyczących tego, czym jest pętla i co stanowi zagnieżdżoną pętlę, …
3
Dwa warianty NP
Oto dwie odmiany definicji NP. (Prawie na pewno) definiują odrębne klasy złożoności, ale moje pytanie brzmi: czy istnieją naturalne przykłady problemów, które pasują do tych klas? (Mój próg, który jest tutaj naturalny, jest nieco niższy niż zwykle). Klasa 1 (nadklasa NP): problemy ze świadkami wielomianowymi, których weryfikacja wymaga czasu wielobiegunowego, …
2
Przykład czegoś innego dla ogólnych i losowych wyroczni?
Niech będzie ogólną wyrocznią w sensie kategorii Cohen / Baire. Niech będzie losową wyrocznią.GGGRRR Czy istnieją klasy złożoności A i B z lub na odwrót, AG=BGandAR≠BRAG=BGandAR≠BR\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^RAG≠BGandAR=BR?AG≠BGandAR=BR?\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?} Pytanie zostało zainspirowane komentarzem Scotta Aaronsona .
2
Czy problem N Queens jest trudny NP?
Problem N-królowej jest następujący: Wejście: N Wynik: umieszczenie N „królowych” na szachownicy NXN w taki sposób, że żadne dwie królowe nie leżą w tym samym rzędzie, kolumnie lub po przekątnej. Przeszukując to w Google, zauważyłem, że wiele slajdów wielu profesorów twierdzi, że jest to trudny problem NP (np. Web.mst.edu/~ercal/387/slides/NP-Hard.ppt) Jednak …
4
Związek między złożonością obliczeniową a informacją
Pracuję w obliczeniowym laboratorium neuronauki, które ocenia ilościowo wzajemną informację między parami lub grupami neuronów. Ostatnio szef skupił się na pomiarze „złożoności dynamiki neuronowej”. Prowadząc tę ​​linię badań, niektórzy ludzie w mojej grupie wydają się utożsamiać „kompleks” z „ma wysoką entropię”. Czy ktoś może wskazać mi związek między złożonością obliczeniową …
2
Minimalny True Monotone 3SAT
Interesuje mnie odmiana SAT, w której wzór CNF jest monotoniczny (żadnych zmiennych nie neguje się). Taka formuła jest oczywiście zadowalająca. Ale powiedzmy, że liczba prawdziwych zmiennych jest miarą tego, jak dobre jest nasze rozwiązanie. Mamy więc następujący problem: MINIMALNY PRAWDZIWY MONOTON 3SAT INSTANCJA: Zestaw U zmiennych, zbiór C rozłącznych klauzul …
1
Jak trudno jest zdecydować o istnieniu idealnego dopasowania czerwono-niebieskiego?
Idealnym rozwiązaniem dwukolorowego dopasowania jest decyzja, czy wykres ma koloryt w dwóch kolorach, tak aby każdy węzeł miał dokładnie jednego sąsiada tego samego koloru co on sam. Schaefer udowodnił, że problem jest NP-zupełny . Pozostaje NP-kompletny nawet dla płaskich wykresów sześciennych. Interesuje mnie wariant, w którym chcemy zdecydować, czy wykres …
1
Przeszkoda taka jak ETH
Wiemy, że pod miT.H.ETHETH nie możemy rozwiązać K.KK sumy w czasie fa( K) p o l y( n K.)f(K)poly(nK)f(K)poly(nK) ramach dowolnej funkcji fa( K)f(K)f(K) (zwykle 2)O ( K)2O(K)2^{O(K)} ). Czy istnieje przypuszczenie, które zapobiega złożoności ( logn )O ( K)(log⁡n)O(K)(\log n)^{O(K)} (jest to całkowicie zgodne z możliwością, ponieważ K.= Ω …
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.