Pytania otagowane jako cc.complexity-theory

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

2
Niekonstruowalne funkcje i nietypowe wyniki
W książce Arora-Barak w definicji funkcji konstruowalnych w czasie mówi się, że użycie funkcji, które nie są konstruowalne w czasie, może prowadzić do „anomalnych wyników”. Czy ktoś ma przykład takiego „anomalnego wyniku”? Słyszałem w szczególności, że mogą istnieć funkcje, których nie utrzymuje twierdzenie o hierarchii czasu, czy ktoś ma przykład …
2
Czy niedeterministyczne automaty do chodzenia po drzewie są silniejsze niż te deterministyczne?
Aktualizacja: Wygląda na to, że ten problem został niedawno zbadany i rozwiązany, zobacz ten artykuł wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton A także tę ankietę: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Załóżmy, że zamiast zwykłego zestawu słów {0,1} *, nasze słowa nie są liniowe, ale raczej podane na jakiejś strukturze drzewa. Aby zapobiec „zagubieniu się” naszych maszyn, zdefiniuj …
3
Trudność ze znalezieniem co najwyżej słowa
Opis problemu: Pozwolić MMM być (potencjalnie niedeterministycznym) automatem wypychającym i pozwól AA\cal Abyć jego alfabetem wejściowym. Czy jest jakieś słowo?w∈A∗w∈A∗w \in \cal A^* św |w|≤k|w|≤k|w| \leq k które jest akceptowane przez MMM ? Czy ten problem NP-jest kompletny? Czy zostało to zbadane? Czy istnieje algorytm pozwalający znaleźć takie słowo?
1
Ukryte stałe w złożoności algorytmów
W przypadku wielu problemów algorytm o największej złożoności asymptotycznej ma bardzo duży stały współczynnik, który jest ukryty przez dużą notację O. Dzieje się tak w przypadku mnożenia macierzy, mnożenia liczb całkowitych (w szczególności najnowszego algorytmu mnożenia liczb całkowitych O (n log n) Harveya i van der Hoevena), sieci sortowania o …
1
Jakie jest odniesienie do pierwszego twierdzenia Gödela o niekompletności opartego na nierozstrzygalności problemu zatrzymania?
Słabsza forma pierwszego twierdzenia Gödela o niekompletności, którego bezpośrednie dowody są w sposób Gödela długotrwałe, zaangażowane, aw niektórych miejscach raczej sprzeczne z intuicją, ma prosty i intuicyjny dowód oparty na nierozstrzygalności problemu zatrzymania - patrz na przykład https: / /en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof Kto pierwszy zaproponował ten dowód iw jakim artykule lub książce …
4
Wyniki ładowania początkowego, które naprawdę się ładują
Istnieje rodzaj wyników w TCS, zwykle nazywany wynikami ładowania początkowego . Ogólnie rzecz biorąc, ma formę Jeśli twierdzenie zachowuje, to twierdzenie zachowuje.ZAZAAA′ZA′A' gdzie AZAAa to zdania, które wyglądają podobnie, a wydaje się „słabsze” niż , dlatego nazywamy ten typ wyników. Podam kilka konkretnych przykładów:A′ZA′A'AZAAA′ZA′A' Twierdzenie. [Chen and Tell, STOC'19] Napraw …
1
Najbardziej znane asymptotyczne rozmiary PCP / 3-SAT
Jakie są najbardziej znane asymptotyczne górne granice wielkości dowodów probabilistycznie sprawdzalnych? Idealnie szukam współczesnej ankiety dotyczącej tego szerokiego pytania, ale jeśli jej nie ma, szczególnie interesuje mnie niedopuszczalność 3-SAT. Niech 7/8 + ε-3-SAT będzie 3-SAT z obietnicą, że jeśli 7/8 + ε część klauzul jest zadowalająca, to instancja jest zadowalająca. …
5
Czy sieci neuronowe można wykorzystać do opracowania algorytmów?
Po coraz większych sukcesach sieci neuronowych w grach planszowych wydaje się, że następnym celem, który wyznaczyliśmy, może być coś bardziej przydatnego niż pokonanie ludzi w Starcraft. Dokładniej, zastanawiałem się, czy Czy sieci neuronowe można przeszkolić do rozwiązywania klasycznych problemów algorytmicznych? Mam na myśli, że na przykład sieć otrzyma wykres wejściowy …
2
Czy istnieje problem obliczeniowy, który występuje w quasi-wielomianowym czasie, ale (być może) go nie ma
Czas quasi-wielomianowy, w skrócie QP, jest klasą złożoności na deterministycznej maszynie Turinga. Oto dokładna definicja: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp Podczas gdy βP jest klasą złożoności o ograniczonym niedeterminizmie. Oto dokładna definicja: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap Łatwo zauważyć, że dowolna maszyna βP może być symulowana przez maszynę QP, a mianowicie βP ⊆⊆\subseteq QP. Ale czy mamy przykład …
2
Liczba minimalnych DFA wielkości co najwyżej ?
Niech będzie alfabetem wielkości i rozważmy minimalne DFA, których rozmiar jest ograniczony co najwyżej . Niech oznacza liczbę różnych takich minimalnych DFA.ΣΣ\Sigma222mmmf(m)f(m)f(m) Czy możemy znaleźć formułę zamkniętą dla ?f(m)f(m)f(m) Biorąc pod uwagę, że dla funkcją przejścia DFA o wielkości co najwyżej jest wykres. Ponieważ stopień węzłów jest ograniczony przez , …
1
Czy możliwe jest zwiększenie kwadratowego niedeterminizmu przyspieszenia obliczeń deterministycznych?
Jest to kontynuacja niedeterministycznego przyspieszenia obliczeń deterministycznych . Czy jest prawdopodobne, że niedeterminizm (lub bardziej ogólnie przemienność) pozwoliłby na ogólne kwadratowe przyspieszenie obliczeń deterministycznych? Czy są jakieś znane nieprawdopodobne konsekwencje czegoś takiego DTime(n2)⊆NTime(n)DTime(n2)⊆NTime(n)\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)?
1
Czy 1-w-3 SAT pozostaje NP-twardy, nawet jeśli każda zmienna występuje zarówno pozytywnie, jak i negatywnie?
Standardowy problem 1-w-3 SAT (lub XSAT lub X3SAT) to: Instancja : formuła CNF z każdą klauzulą ​​zawierającą dokładnie 3 literały Pytanie : czy istnieje zadowalające ustawienie przypisania dokładnie 1 literał na klauzulę prawda? Problem jest NP-zupełny i pozostaje trudny, nawet jeśli żadna zmienna nie zostanie zanegowana. Zastanawiam się, czy problem …
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.