Teoretyczne informatyka

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

1
Jaka jest złożoność tej gry?
To jest uogólnienie mojego poprzedniego pytania . Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle . Początkowo jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech będzie ciągiem znaków.MMMAAAAAAxxx Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio …
1
Techniki dowodowe pokazujące, że sprawdzanie typu zależnego jest rozstrzygalne
Jestem w sytuacji, w której muszę pokazać, że sprawdzanie typu ma decydujący wpływ na rachunek różniczkowy, nad którym pracuję. Do tej pory udało mi się udowodnić, że system silnie się normalizuje, a zatem równość definicyjna jest rozstrzygalna. W wielu źródłach, które czytam, rozstrzygalność sprawdzania typów jest wymieniona jako następstwo silnej …
1
Szybka klasyczna symulacja algorytmów kwantowych
Czy istnieją przykłady przypadków, w których klasyczna symulacja algorytmu kwantowego dla problemu przewyższa najlepiej znany wcześniej klasyczny algorytm dla tego problemu? „Lepsze wyniki” nie musi oznaczać innej klasy złożoności, może po prostu być lepsze skalowanie. To pytanie zostało zainspirowane przypadkiem wydajnej klasycznej symulacji kwantowego algorytmu rekomendacji .
1
Czy ta gra jest EXPSPACE?
Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle A . Początkowo A jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech x będzie ciągiem znaków.M.MMZAAAZAAAxxx Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio i m B dolarów. …
2
Powszechny wgląd w hipotetyczną złożoność problemów graficznych
Natknąłem się na dwa przykłady hipotetycznej twardości niektórych problemów graficznych. Hipotetyczna twardość oznacza, że ​​obalenie niektórych przypuszczeń oznaczałoby zupełność NP odpowiedniego problemu grafowego. Na przykład, hipoteza Barnette'a stwierdza, że ​​każdy 3-połączony sześcienny dwuwymiarowy wykres jest hamiltonianem. Feder i Subi udowodnili, że obalenie przypuszczenia oznaczałoby zupełność NP problemu cyklu hamiltonowskiego na …
3
Czy warto regularnie czytać artykuły poza swoją dziedziną?
Co sądzisz o regularnym czytaniu artykułów poza własną dziedziną, nawet tych niezwiązanych z jego obszarem? Moją intuicją jest to, że może dać zupełnie inną perspektywę lub technikę, która może pomóc mi w moich własnych problemach. Ale jednocześnie jestem trochę sceptyczny, ponieważ strata czasu będzie, jeśli nowa wiedza nie pomoże mu …
1
Na rzadkich kompletach i P vs L.
Twierdzenie Mahaneya mówi nam, że jeśli istnieje rzadki zestaw przy wielomianowych redukcjach wielokrotności jeden, to . (Patrz „ Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa ”)NPNPNPP=NPP=NPP = NP Czy znane są konsekwencje istnienia rzadkich kompletnych zestawów dla innych klas złożoności? W szczególności, jeśli w obszarze logarytmicznym występuje …
1
Algorytmy inwersji programów dla programów wyższego rzędu
Termin inwersja programu ma wiele odcieni znaczenia, ale prawdopodobnie zaczął się od pracy J. McCarthy'ego z 1956 r. Inwersja funkcji zdefiniowanych przez maszyny Turinga w kontekście sztucznej inteligencji. Do tej pory odkryto wiele połączeń między inwersją programu a innymi polami, np. Programowanie odwracalne (fizyczne i logiczne), częściowa ocena, weryfikacja, programowanie …
1
Znajdź przybliżony argmax, używając tylko przybliżonych maksymalnych zapytań
Rozważ następujący problem. nnnv1,⋯,vn∈Rv1,⋯,vn∈Rv_1, \cdots, v_n \in \mathbb{R}S⊆{1,⋯,n}S⊆{1,⋯,n}S \subseteq \{1,\cdots,n\}maxi∈Svimaxi∈Svi\max_{i \in S} v_i Ten problem jest prosty: możemy użyć wyszukiwania binarnego, aby znaleźć argmax z zapytaniami . tj. Zbuduj kompletne drzewo binarne z liści odpowiadających indeksom. Zacznij od korzenia i zejdź do liścia w następujący sposób. W każdym węźle zapytaj …
1
Równowaga w grze w postój
Rozważ następującą grę 2-osobową: Natura losowo wybiera program Każdy gracz gra liczbę w [0, nieskończoność] włącznie w odpowiedzi na ruch natury Weź minimalną liczbę graczy i uruchom program dla (maksymalnie) tak wielu kroków (chyba że obaj gracze wybiorą nieskończoność) Jeśli program się zatrzyma, gracz, który zagrał minimalną liczbę, otrzymuje 1 …
1
Decydowanie o najbardziej znaczącym mnożeniu binarnym
Interesuje mnie określenie złożoności następującego problemu decyzyjnego: Biorąc pod uwagę dwie liczby całkowite i l 2 (każda z co najwyżej m bitami), zdecyduj, czy najbardziej znaczącym bitem z mnożenia l 1 ⋅ l 2 jest 1 (gdzie wynik jest drukowany w 2-bitowych bitach z możliwymi początkowymi zerami)?l1l1l_1l2)l2l_2l1⋅ l2)l1⋅l2l_1 \cdot l_2 …
1
Sortowanie ze średnią porównań
Czy istnieje algorytm sortowania oparty na porównaniu, który wykorzystuje średnie porównania ?lg(n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) Istnienie algorytmu porównania najgorszego przypadku jest otwartym problemem, ale średni przypadek wystarcza dla algorytmu losowego z oczekiwanym porównania dla każdego wkładu. Znaczenie polega na tym, że są to porównania o (n) z optymalnych, marnując średnio tylko o (1) …
1
Rozkład relacji binarnej na pojemniki w taki sposób, że każdy element znajduje się w niewielkiej liczbie pojemników
Dostajemy pary obiektów (powiedzmy liczby). Każdy obiekt pojawia się w co najwyżej qqq parach. Naszym celem jest rozdzielenie par na pojemniki o równej wielkości, tak aby każdy obiekt występował w jak najmniejszej liczbie różnych pojemników. Dokładniej, interesuje nas funkcja fff z właściwością, że dla każdej relacji binarnej z parami mmm …
1
Porównywanie dwóch produktów z list liczb całkowitych?
Załóżmy, że mam dwie listy liczb całkowitych dodatnich o ograniczonej męskości i biorę iloczyn wszystkich elementów każdej listy. Jaki jest najlepszy sposób ustalenia, który produkt jest większy? Oczywiście mogę po prostu obliczyć każdy produkt, ale mam nadzieję, że istnieje bardziej wydajne podejście, ponieważ liczba cyfr w produktach wzrośnie liniowo wraz …
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.