Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Jakie są złożoności następujących podzbiorów SAT?
Załóżmy, żeP.≠ N.P.P≠NPP \neq NP Do tetracji użyj następującego zapisu (tj. ).jazaia{}^iajaa = aza⋅⋅⋅zaja razyia=aa⋅⋅⋅a⏟i times{}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}} | x | jest wielkością instancji x. Niech L będzie językiem,L |fa( i ) ≤ | x | &lt; g( i ):={x∈L | ∃i∈N, f(i)≤|x|&lt;g(i)}L|f(i)≤|x|&lt;g(i):={x∈L | ∃i∈N, f(i)≤|x|&lt;g(i)}L|_{f(i)\leq |x| < …
3
Czy osadzenie rozwiązania jest możliwe dla SAT?
Interesują mnie „twarde” pojedyncze przypadki problemów z NP. Ryan Williams omówił problem SAT0 na blogu Richarda Liptona . SAT0 pyta, czy instancja SAT ma konkretne rozwiązanie składające się ze wszystkich zer. To skłoniło mnie do myślenia o konstruowaniu instancji SAT, które prawdopodobnie będą „trudne”. Rozważmy wystąpienie SAT z klauzulami i …
1
Twardość problemu z ograniczonym układem gwiezdnym?
Układ gwiazda rodziny n podzbiorów n-elementów przedstawionych . System położony jest graficznym, jeżeli jest jakiś wykres tak, że jest rodzina sąsiedztwie wierzchołków w . To jest kompletne, aby zdecydować, czy dany układ gwiezdny jest graficzny.S G ( V , E ) F G N PFFFSSSG(V,E)G(V,E)G(V,E)FFFGGGNPNPNP Jaka jest minimalna wystąpienie każdego …
5
Klasy złożoności dla przypadków innych niż „najgorszy przypadek”
Czy mamy klasy złożoności w odniesieniu do, powiedzmy, złożoności średnich przypadków? Na przykład, czy istnieje (nazwana) klasa złożoności dla problemów, których podjęcie wymaga wielomianu? Kolejne pytanie dotyczy złożoności najlepszych przypadków , których przykłady przedstawiono poniżej: Czy istnieje klasa (naturalnych) problemów, których decyzja wymaga co najmniej wykładniczego czasu? Aby to wyjaśnić, …
1
Czy badano derandomizację lekko niejednorodnych klas, np. BPP / liniowy?
Przez BPP / linear mam na myśli maszyny BPP z liniową radą, która spełnia obietnicę, gdy otrzyma „prawidłową” radę, a derandomizacja powinna dać nam, powiedzmy, algorytm P / liniowy lub (SUBEXP / liniowy). Jeśli zastosujemy niejednolite założenia, uważam, że klasyczne wyniki powinny zadziałać, ponieważ możemy „oszukać” niejednolitych przeciwników. Jednak przy …
2
Dolne granice dla liniowego problemu satysfakcji
W SODA 1995 Jeff Erickson wykazały niższe granice liniowego spełnialności (sprawdzenie, czy niektóre -subset z n liczb rzeczywistych spełnia równanie liniowe o r zmiennych). Metoda dowodowa wykorzystuje nieskończenie małe i zasadę transferu Tarskiego .rrrnnnrrr Czy ktoś mógłby wyjaśnić intuicję, jaką kryje się za tą trasą, aby udowodnić tę granicę? Jaka …
3
Co dowody na to, że
Co dowody na to, że ?c o R P≠ N.P.coRP≠NPcoRP \neq NP jest klasą języków, dla których istnieje probabilistyczna maszyna Turinga, która działa w czasie wielomianowym i zawsze odpowiada Tak na dane wejściowe należące do języka i odpowiada Nie z prawdopodobieństwem co najmniej połowy na dane wejściowe nienależące do języka …
2
Czy istnieje oficjalna nazwa pojęcia „uniwersalnego użytku”?
Istnieje kilka różnych (prawdopodobnie nierównych) pojęć uniwersalności obliczeniowej (patrz na przykład kilka ostatnich stron http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) i nie ma zgody między eksperci o tym, które pojęcia są najbardziej poprawne (patrz na przykład http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ). Próbuję powiedzieć coś o konkretnym modelu obliczeń biomolekularnych. Chciałbym argumentować, że jest „bardziej uniwersalny” lub „bardziej …
2
Tasowanie tokenów na wykresie za pomocą lokalnych zamian
Niech będzie nieregularnym połączonym wykresem, którego stopień jest ograniczony. Załóżmy, że każdy węzeł zawiera unikalny token.G = ( V, E)G=(V,E)G= (V, E) Chcę równomiernie tasować tokeny między wykresami, używając tylko lokalnych zamian (tj. Wymiany tokenów między dwoma sąsiadującymi węzłami)? Czy znana jest dolna granica tego problemu? Jedyny pomysł, jaki miałem, …
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.