Pytania otagowane jako cc.complexity-theory

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

1
Czy programowanie dynamiczne nigdy nie jest słabsze niż chciwy?
W złożoności obwodu mamy rozdzielenia mocy różnych modeli obwodów. W złożoności dowodu mamy rozróżnienia między mocami różnych systemów dowodu. Ale w algorytmie wciąż mamy tylko kilka różnic między potęgami paradygmatów algorytmicznych . Moje pytania poniżej mają na celu dotknięcie tego ostatniego problemu w dwóch paradygmatach: Chciwy i Programowanie dynamiczne. Mamy …
1
2FA złożoność stanu k-Clique?
W prostej formie: Można dwukierunkowa skończony automat rozpoznaje vvv wykresy -Vertex które zawierają trójkąt z o(v3)o(v3)o(v^3) stany? Detale Zainteresowania są tu vvv wykresy -Vertex kodowane przy użyciu sekwencji krawędzi, każda krawędź jest para różnych wierzchołki {0,1,…,v−1}{0,1,…,v−1}\{0,1,\dots,v-1\} . Załóżmy, że (Mv)(Mv)(M_v) jest ciągiem dwukierunkowy automaty skończone (deterministyczny lub niedeterministyczny), tak że …
1
pełny problem z quasi-wielomianem związanym z liczbą rozwiązań
FewP to klasa z wielomianem ograniczonym liczbą rozwiązań (w wielkości wejściowej). Tam nie jest znana -Complete problem . Interesuje mnie, jak daleko możemy rozciągnąć tę obserwację.N P f e w PNPNPNPNPNPNPfewPfewPfewP Czy istnieje jakiś naturalny problem z uzupełnieniem z quasi-wielomianową górną granicą liczby rozwiązań (świadków)? Czy istnieje powszechnie przyjęte przypuszczenie, …
1
Czy
Co się stanie, jeśli zdefiniujemy P P A D wPPAD{\bf PPAD} taki sposób, że zamiast polytime-maszyny Turinga / obwodu polisize, maszyny logistycznej Turinga lub obwodu A C 0AC0{\bf AC^0} koduje problem? Ostatnio dając szybsze algorytmy Okręgowego spełnialności dla małych obwodów okazało się być ważne, więc zastanawiam się, co się dzieje …
1
Gładka złożoność nieujemnego stałego
Od dwóch dekad trwają fantastyczne prace nad Permanentnym. Przez pewien czas zastanawiałem się nad możliwością zastosowania algorytmu Smooth P dla Permanent of Nonnegative Matrices. Istnieje oczywiście słynny algorytm JSV, ale jest to fpras. Myśląc o innych pracach w ramach wygładzonej złożoności, silną wskazówką bycia w wygładzonym P było istnienie algorytmu …
2
minimalizowanie wielkości wyrażeń regularnych dla zbiorów skończonych
Wiadomo, że minimalizowanie rozmiaru wyrażenia regularnego jest pełne dla PSPACE, nawet jeśli mamy specyfikację języka jako DFA . Jakie są wyniki, jeśli język jest skończony? Problem ten można rozważyć w dwóch modelach: Dane wejściowe to wszystkie ciągi w języku, a rozmiar wejściowy mierzymy sumą długości wszystkich ciągów. Dane wejściowe to …
3
pod względem
Probabilistyczny system zapobiegania jest powszechnie określany jako ograniczenie M A , gdy Arthur można wykorzystać tylko f ( n ) losowe fragmenty i może jedynie zbadanie g ( n ) bitów certyfikat potwierdzający przesłany przez Merlin (patrz: http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).P.doP.[ f( n ) , g( n ) ]P.doP.[fa(n),sol(n)]\mathcal{PCP}[f(n),g(n)]MM.ZA\mathcal{MA}fa( n )fa(n)f(n)sol( n …
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.