wszyscy wiedzą, że istnieje wiele problemów decyzyjnych, które są trudne NP na ogólnych wykresach, ale interesują mnie problemy, które są trudne NP, gdy podstawowy wykres jest ścieżką. Czy możesz mi pomóc w zebraniu takich problemów? Znalazłem już powiązane pytanie dotyczące trudnych NP problemów...
Wiele problemów związanych z grafem algorytmicznym można rozwiązać w czasie wielomianowym zarówno na wykresach nieważonych, jak i ważonych. Niektóre przykłady to najkrótsza ścieżka, min. Drzewo rozpinające, najdłuższa ścieżka (w ukierunkowanych grafach acyklicznych), maksymalny przepływ, min....
To jest pytanie otwarte, za co z góry przepraszam. Czy istnieją przykłady zdań, które (pozornie) nie mają nic wspólnego ze złożonością lub maszynami Turinga, ale odpowiedź na które sugerowałaby ?P≠NPP≠NP\mathbf{P}\neq
Kontynuując poprzednie pytanie , jakie są najlepsze obecne dolne granice przestrzeni dla SAT? Przez spację dolną rozumiem tutaj liczbę komórek taśmy roboczej używanych przez maszynę Turinga, która używa binarnego alfabetu taśmy roboczej. Stały składnik addytywny jest nieunikniony, ponieważ TM...
W artykule „KOMPLEKSOWOŚĆ PROBLEMÓW Z ZADOWOLENIEM” Tomasza J. Schaefera autor wspomniał, że This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity...
Czytałem, że początkowo Kościół zaproponował -calculus jako część swoich postulatów z logiki (co jest gęstym odczytem). Ale Kleene udowodnił, że jego „system” jest niespójny, po czym Church wyodrębnił odpowiednie rzeczy do swojej pracy nad „skutecznym obliczeniem” i porzucił wcześniejsze prace nad...
W przypadku algorytmów losowych przyjmujących rzeczywiste wartości „sztuczka medianowa” jest prostym sposobem zmniejszenia prawdopodobieństwa niepowodzenia do dowolnego progu , kosztem tylko wielokrotności narzut. Mianowicie, jeśli wyjście mieści się w „dobrym zakresie” z prawdopodobieństwem (co...
Czytałem artykuł Andreja Bauera Pierwsze kroki w teorii obliczeń syntetycznych . Na zakończenie zauważa to Nasza aksjatyzacja ma swoje granice: nie może udowodnić żadnych wyników w teorii obliczeń, które nie relatywizują się do obliczeń wyroczni. Jest tak, ponieważ teorię można interpretować...
W tym wątku próba próby Norbet Bluma jest zwięźle obalona przez odnotowanie, że funkcja Tardos jest przeciwne do Twierdzenia 6.P.≠ N.P.P≠NPP \neq NP Twierdzenie 6 : Niech będzie dowolną monotoniczną funkcją boolowską. Załóżmy, że istnieje aproksymator A CNF-DNF, którego można użyć do udowodnienia...
Niech zmiennymi będą . Odległość między dwiema zmiennymi jest zdefiniowana jako. Odległość między dwoma literałami jest odległością między odpowiednimi dwiema zmiennymi. d ( x a , x b ) = | a - b |x1, x2), x3). . . xnx1,x2,x3...xnx_1 , x_2 , x_3 ... x_nre( xza, xb) = | a - b |d(xa,xb)=|a−b|d(x_a ,...
Czy istnieje dobra ankieta, która porównuje różne ekstraktory, koncentratory i superkoncentratory i określa najlepsze metody pod względem kompromisu między losowością, czasem i przestrzenią?
Dowód separacji klas złożoności używa jednorodności klas złożoności zasadniczo, jeśli dowód nie dowodzi wyniku dla wersji niejednorodnej, na przykład dowody oparte na przekątnej (takie jak twierdzenia dotyczące hierarchii czasu i przestrzeni) w istotny sposób wykorzystują jednolitość, ponieważ...
Wiemy dużo o ograniczeniach obwodów o stałej głębokości (rozmiar wielomianowy). Ponieważ formuły o stałej głębokości (rozmiar wielomianowy) są jeszcze bardziej ograniczonym modelem obliczeń, wszystkie problemy, o których wiadomo, że nie występują w AC 0, również nie są obliczalne na podstawie wzoru...
Jakie są interesujące różnice między teorią a praktyką bezpieczeństwa i kryptografii? Najciekawsze będą oczywiście przykłady sugerujące nowe kierunki badań teoretycznych w oparciu o praktyczne doświadczenia :). Odpowiedzi mogą obejmować (ale nie wyłącznie): Przykłady, w których teoria sugeruje,...
Jeśli jest funkcją wypukłą, to nierówność Jensena stwierdza, że i mutatis mutandis, gdy jest wklęsłe. Oczywiście w najgorszym przypadku nie można górnej granicy w kategoriach dla wypukłego , ale czy istnieje granica, która idzie w tym kierunku, jeśli jest wypukły, ale „niezbyt wypukły”? Czy...
Zadałem już to pytanie jakiś czas temu na MathOverflow , ale zgodnie z moją najlepszą wiedzą jest ono nadal otwarte, więc zamieszczam je ponownie w nadziei, że ktoś o nim usłyszy. Opis problemu Niech , i będą trzema partycjami w niepustych częściach (oznaczonych przez , i ) zestawu { }. Znajdź...
Czy ktoś mógłby wskazać jedną lub więcej stron internetowych, z których można pobrać działającą implementację solvera #SAT? Interesują mnie osoby zwracające dokładną liczbę rozwiązań, a nie
Czy BQP jest równe BPP z dostępem do ukrytej podgrupy
Podczas zestawiania wyników często pożądane jest, aby mieć diagramy wyglądające profesjonalnie, a nie diagramy zestawione w MS Paint. Jaki jest standard rysowania struktur
(Von Neumann podał algorytm, który symuluje uczciwą monetę, mając dostęp do identycznych monet o tendencyjnym charakterze. Algorytm ten potencjalnie wymaga nieskończonej liczby monet (choć w oczekiwaniu wystarcza ostatecznie ich wiele). Pytanie dotyczy przypadku, gdy dozwolona liczba rzutów monetą...