Pytania otagowane jako polynomial-time

4
Dlaczego 2SAT w P?
Natknąłem się na algorytm wielomianowy, który rozwiązuje 2SAT. Uważam za zaskakujące, że 2SAT znajduje się w P, gdzie wszystkie (lub wiele innych) instancji SAT są NP-Complete. Co wyróżnia ten problem? Co sprawia, że ​​jest to takie proste (NL-Complete - nawet łatwiejsze niż P)?
2
Jakie klasy programów matematycznych można rozwiązać dokładnie lub w przybliżeniu w czasie wielomianowym?
Jestem raczej zdezorientowany literaturą o ciągłej optymalizacji i literaturą TCS o tym, które rodzaje (ciągłych) programów matematycznych (MP) można skutecznie rozwiązać, a które nie. Wydaje się, że społeczność ciągłej optymalizacji twierdzi, że wszystkie programy wypukłe można skutecznie rozwiązać, ale uważam, że ich definicja „wydajnego” nie pokrywa się z definicją TCS. …
2
Czy istnieje algorytm wielomianowy do określania, czy rozpiętość zbioru macierzy zawiera macierz permutacji?
Chciałbym znaleźć algorytm wielomianowy, który określa, czy rozpiętość danego zestawu macierzy zawiera macierz permutacji. Jeśli ktoś wie, czy ten problem ma inną klasę złożoności, byłoby to równie pomocne. EDYCJA: Oznacziłem to pytanie za pomocą programowania liniowego, ponieważ mam poważne podejrzenia, że ​​gdyby istniało takie rozwiązanie, byłby to rodzaj algorytmu programowania …
1
Czy można rozpoznać w wieloskładnikowej probabilistycznej przestrzeni sublogarytmicznej?
Zastanów się nad językiem .EQUALITY={anbn∣n≥0}EQUALITY={anbn∣n≥0} \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} Wiadomo, że nie może zostać rozpoznany przez żadną maszynę Turinga (ATM) na przemian z przestrzenią sublogarytmiczną (Szepietowski, 1994) . (Istnieje bankomat wykorzystujący przestrzeń sublogarytmiczną dla członków, ale nie dla wszystkich osób niebędących członkami!)EQUALITYEQUALITY \mathtt{EQUALITY} Z drugiej …
3
Jak szybko możemy rozwiązać całkowicie nieimodularny program liniowy liczb całkowitych?
(Jest to kontynuacja tego pytania i odpowiedzi ). Mam następujący całkowicie nieimodularny (TU) całkowity program liniowy (ILP). Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych x i j jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całkowite:ℓ , m , n1, n2), …
6
Czy istnieje naturalny problem w czasie quasi-wielomianowym, ale nie w czasie wielomianowym?
László Babai niedawno udowodnił, że problem z izomorfizmem grafowym występuje w quasipolomomialnym czasie . Zobacz także jego przemówienie na Uniwersytecie w Chicago, notatkę z przemówień Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 . Zgodnie z twierdzeniem LADNER, o ile P.≠NP.P≠N.P.P \neq NP , a …
5
Jakie znaczące modele automatów mają wielomianowo rozstrzygalne ograniczenie?
Próbuję rozwiązać konkretny problem i pomyślałem, że mogę go rozwiązać za pomocą teorii automatów. Zastanawiam się, jakie modele automatów mają rozstrzygające rozstrzyganie w czasie wielomianowym? tzn. jeśli masz maszyny M.1, M2)M.1,M.2)M_1, M_2 , możesz sprawdzić, czy wydajnie.L ( M1) ⊆ L ( M2))L.(M.1)⊆L.(M.2))L(M_1) \subseteq L(M_2) Oczywiste, które przychodzą na myśl, …
2
Biorąc pod uwagę 4-cyklowy wykres , czy możemy ustalić, czy ma on 3-cykl w czasie kwadratowym?
Problem z rowem jest następujący:kkk Instancja: Niekierowany wykres z wierzchołkami i do n \ wybierz 2 krawędzie.nsolsolGnnn( n2))(n2))n \choose 2 Pytanie: Czy w G istnieje (właściwy) cykl K ?kkksolsolG Tło: Dla każdego ustalonego kkk możemy rozwiązać cykl 2 tys2)k2k w czasie O ( n2))O(n2))O(n^2) . Raphael Yuster, Uri Zwick: Znalezienie …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
3
Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS)
Odpowiedź: nieznana. Zadawane pytania są naturalne, otwarte i pozornie trudne; pytanie jest teraz wiki społeczności. Przegląd Pytanie ma na celu podzielenie języków należących do klasy złożoności - wraz z maszynami decyzyjnymi Turinga (TM), które akceptują te języki - na dwie uzupełniające się podklasy:PPP języki gnostyczne i bazy TM (które można …
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.