Teoretyczne informatyka

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

2
Ogromna współpraca online w celu rozwiązania otwartego problemu w informatyce teoretycznej
W projektach Polymath duża grupa pracuje nad otwartym problemem. Jakie problemy wydają się działać najlepiej w tych ramach? Czy są jacyś dobrzy kandydaci na projekt polimorficzny w informatyce teoretycznej? Czy są jakieś przeszkody, które sprawiają, że projekty Polymath rzadziej odnoszą sukcesy w informatyce teoretycznej w porównaniu z innymi dziedzinami matematyki?
2
Problemy bez znanej przewagi kwantowej
Zastanawiałem się, jaka jest lista obecnych naturalnych problemów obliczeniowych, dla których nie ma znanej przewagi złożoności przy użyciu komputera kwantowego. Na początek, myślę, że obliczenie odległości edycji jest tym, dla którego najszybszy znany algorytm kwantowy wydaje się być najszybszym znanym klasycznym. Mówiąc bardziej wstępnie, sugerowałbym również sortowanie jako kolejny problem, …
1
Dlaczego Tomita stworzył GLR i nie używał Earleya?
Kiedy patrzę na parsowanie Earleya, wygląda to bardzo elegancko i zastanawiam się, dlaczego techniki GLR stały się popularne? Czy ktoś wie, co było nie tak z analizowaniem Earleya przez to, że Tomita stworzyła GLR? Wydajność? Wszelkie publikacje dotyczące tych dyskusji są bardzo mile widziane.
11 parsing 
3
Dla jakich języków istnieje już teoria równoważności obserwacyjnej?
Dla potwierdzenia poprawności szukam użytecznego pojęcia równoważności programu dla systemów czystego typu (PTS) Barendregta; brakuje tego, dla wystarczającej liczby systemów określonego typu. Moim celem jest po prostu użycie tego pojęcia, a nie badanie go dla samego siebie.≅≅\cong Pojęcie to powinno być „ ekstensywne ” - w szczególności, aby udowodnić, że …
3
Czy
Oznacz przez minimalny stopień wyjściowy w G , a przez δ - ( G ) minimalny stopień wyjściowy.δ+(G)δ+(G)\delta^+(G)GGGδ−(G)δ−(G)\delta^-(G) W powiązanym pytaniu wspomniałem o rozszerzeniu Ghouili-Houri twierdzenia Diraca o cyklach hamiltonowskich , co sugeruje, że jeśli to G oznacza hamiltonian.δ+(G),δ−(G)≥n2δ+(G),δ−(G)≥n2\delta^+(G),\delta^-(G) \geq \frac{n}{2} W swoim komentarzu Saeed skomentował inne rozszerzenie, które wydaje …
2
2DFA, która wymaga wielu stanów w równoważnym DFA?
Czy istnieje 2DFA ze stanami (gdzie n nie jest łatwe, powiedzmy co najmniej 4), które wymagają co najmniej 2 n stanów do symulacji przy użyciu dowolnego DFA?nnnnnn2)n2n2^n Dwukierunkowy DFA (2DFA) jest deterministyczny automat skończony-państwo, które może poruszać się tam iz powrotem na jej taśmie tylko do odczytu wejścia, w przeciwieństwie …
2
Czy problem N Queens jest trudny NP?
Problem N-królowej jest następujący: Wejście: N Wynik: umieszczenie N „królowych” na szachownicy NXN w taki sposób, że żadne dwie królowe nie leżą w tym samym rzędzie, kolumnie lub po przekątnej. Przeszukując to w Google, zauważyłem, że wiele slajdów wielu profesorów twierdzi, że jest to trudny problem NP (np. Web.mst.edu/~ercal/387/slides/NP-Hard.ppt) Jednak …
1
Znalezienie podwójnego wykresu
Według książki Topological Graph Theory autorstwa Grossa i Tuckera, biorąc pod uwagę komórkowe osadzenie wykresu na powierzchni (przez „powierzchnię” rozumiem tutaj kulę z pewnymi uchwytami , a poniżej odnosi się do kuli o dokładnie uchwyty), można zdefiniować podwójny multigraf, traktując twarze osadzonego wykresu jako wierzchołki i dodając krawędź między dwoma …
4
Związek między złożonością obliczeniową a informacją
Pracuję w obliczeniowym laboratorium neuronauki, które ocenia ilościowo wzajemną informację między parami lub grupami neuronów. Ostatnio szef skupił się na pomiarze „złożoności dynamiki neuronowej”. Prowadząc tę ​​linię badań, niektórzy ludzie w mojej grupie wydają się utożsamiać „kompleks” z „ma wysoką entropię”. Czy ktoś może wskazać mi związek między złożonością obliczeniową …
4
Algorytmy aproksymacyjne stosowane w algorytmach dokładnych
Algorytmy aproksymacyjne mogą dawać wynik do pewnego stałego współczynnika. Jest to nieco mniej satysfakcjonujące niż dokładne algorytmy. Jednak stałe czynniki są ignorowane w złożoności czasowej. Zastanawiam się więc, czy następująca sztuczka jest możliwa lub została zastosowana, aby rozwiązać jakiś problem :B ∘ Ab∘ZAB \circ A Użyj algorytmu aproksymacyjnego rozwiązującego problem …
2
Minimalny True Monotone 3SAT
Interesuje mnie odmiana SAT, w której wzór CNF jest monotoniczny (żadnych zmiennych nie neguje się). Taka formuła jest oczywiście zadowalająca. Ale powiedzmy, że liczba prawdziwych zmiennych jest miarą tego, jak dobre jest nasze rozwiązanie. Mamy więc następujący problem: MINIMALNY PRAWDZIWY MONOTON 3SAT INSTANCJA: Zestaw U zmiennych, zbiór C rozłącznych klauzul …
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.