Teoretyczne informatyka

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

1
Literatura wokół NP vs EXPTIME
Nawet jeśli nie jest to kluczowa kwestia, nie widzę żadnej literatury wokół tego pytania. Czy są wyniki relatywizacji? Czy nie byłoby łatwo udowodnić ścisłe włączenie poprzez dostosowanie niedeterministycznego twierdzenia o hierarchii czasu poprzez badanie wszystkich możliwych ścieżek maszyny NP?
5
Jak decydujesz, kiedy masz wystarczająco dużo wyników badań, aby napisać artykuł i do którego czasopisma wysyłasz artykuł
W niektórych obszarach badań w CS otrzymaliśmy bardzo interesujące wyniki. Teraz myślimy o ich opublikowaniu. W naszej grupie filozofią jest publikowanie w gazetach konferencyjnych natychmiast drobiazgów, co jest w porządku, ale nie najlepsze. Teraz myślę o zebraniu większej liczby tych „drobiazgów” i opublikowaniu ich w pracy JCR, o współczynniku wpływu …
2
Czy istnieją jakieś „graficzne” algebry, które mogą opisać „kształt” wykresów?
Jednym z głównych problemów w wyliczaniu wykresów jest określenie „kształtu” wykresu, np. Klasy izomorfizmu dowolnego konkretnego wykresu. Jestem w pełni świadomy, że każdy wykres może być reprezentowany jako macierz symetryczna. Jednak, aby uzyskać jego kształt, potrzebujesz kolekcji permutacji wierszy / kolumn, co czyni matrycę nieco mniej odpowiednią. Trudniej jest też …
1
Języki zapytań do baz danych dla wydajnych zapytań
Wydaje się, że w popularnych językach zapytań dotyczących relacyjnych baz danych możliwe jest tworzenie zapytań, które będą wymagały dużej ilości zasobów. W praktyce administratorzy baz danych zarządzają tym, ograniczając ilość pamięci na zapytanie i sprawdzając, czy w bazie danych nie ma żadnych długotrwałych zapytań. Wydaje się to raczej ad-hoc, czy …
1
Heurystyka dla optymalizacji
Ponieważ jest piątek, czas na pytanie CW. Szukam heurystyki, która ma szerokie zastosowanie w problemach związanych z optymalizacją. Aby ograniczyć zakres do bardziej „przyjaznej teorii” heurystyki, oto zasady (niektóre arbitralne, niektóre nie) Powinna to być dobrze zdefiniowana metoda bez wielu parametrów i z konkretnym czasem pracy (może na iterację) Powinny …
1
Ograniczanie liczby krawędzi między wykresami gwiazdowymi, tak że wykres jest płaski
Mam wykres solGGktóry składa się tylko z wykresów gwiazd. Wykres gwiezdny składa się z jednego centralnego węzła mającego krawędzie do każdego innego węzła w nim. PozwolićH.1,H.2), ... ,H.nH1,H2,…,HnH_1, H_2, \ldots, H_n być różnymi wykresami gwiazd o różnych rozmiarach, które są obecne w solGG. Nazywamy zbiór wszystkich węzłów, które są centrami …
1
Analiza wygładzona: jeśli problem ma złożoność pseudopolinomialną, czy jest on płynny?
Zafascynowała mnie niezwykła eksplozja w analizie wygładzonej i uderzyło mnie stwierdzenie w artykule Analiza wygładzonego programowania liczb całkowitych . Stwierdzono, że programowanie liniowe w liczbach całkowitych jest wygładzone P, jeśli jest ograniczone wielomianowo. Było to niezbędne, ponieważ programowanie liczb całkowitych jest pseudo-wielomianowe! Pytanie zatem brzmi: Czy to uniwersalnie przenosi się …
2
Maksymalizacja sumarycznych wag krawędzi
Zastanawiam się, czy następujący problem ma nazwę lub wyniki z nim związane. Niech będzie wykresem ważonym, gdzie oznacza wagę krawędzi między i , a dla wszystkich , . Problem polega na znalezieniu podzbioru wierzchołków, który maksymalizuje sumę wag sąsiadujących z nimi krawędzi: Zauważ, że liczę krawędzie, które są wewnątrz podzbioru …
1
Niejednolici kontra Jednolici Przeciwnicy
To pytanie powstało w kontekście kryptografii, ale poniżej przedstawię je w kategoriach teorii złożoności, ponieważ ludzie tutaj są bardziej zaznajomieni z tym ostatnim. To pytanie dotyczy problemów w NP, ale nie w średniej P / poli i pokonania premii przez Oracle Access . Nieformalne oświadczenie: kiedy nierównomiernym przeciwnikom (tj. Wielorakiej …
2
Algorytmy wielomianowe dla UPB (nieusuwalne bazy produktów)
Rozważ przestrzeń Hilberta H.=H.1⊗ ⋯ ⊗H.nH.=H.1⊗⋯⊗H.nH = H_1 \otimes \dots \otimes H_n. Podstawa produktu nie do rozszerzenia (UPB) to zestaw wektorów produktu|vja⟩ = |v1ja⟩ ⊗ ⋯ ⊗ |vnja⟩|vja⟩=|vja1⟩⊗⋯⊗|vjan⟩\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle takie, że: a) wszyscy |vja⟩|vja⟩\vert v_i \rangle są wzajemnie ortogonalne …
1
Decyzja, czy ciąg znaków zastępczych jest całkowicie dopasowany do innego ciągu znaków zastępczych w zestawie
Oto problem, który dręczy mnie od dłuższego czasu. Powiedzmy, że łańcuch jest sekwencją 1 i 0, a łańcuch wieloznaczny to sekwencja 1, 0 i? S. Wszystkie ciągi znaków i symbole wieloznaczne mają tę samą długość. Są to standardowe symbole wieloznaczne UNIX; 10 ?? 1 pasuje do 10011, 10111 itd. - …
2
Rysowanie wykresów ograniczonej liczby skrzyżowań
Twierdzenie Fáry'ego mówi, że prosty wykres płaski można narysować bez przecięć, tak że każda krawędź jest odcinkiem linii prostej. Moje pytanie brzmi, czy istnieje analogiczne twierdzenie dla grafów ograniczonej liczby skrzyżowań . W szczególności, czy możemy powiedzieć, że można narysować prosty wykres z liczbą przecięcia k, aby na rysunku było …
1
Jaka jest klasyfikacja złożoności teorii portfela w ekonomii finansowej?
Jak wszyscy wiecie, kryzys finansowy z 2008 r. Ciągle wypada. Zastanawiałem się, jak teoria złożoności pasuje do tego wszystkiego, kiedy zdałem sobie sprawę, że nie znam podstawowych klas złożoności związanych z ekonomią finansową. Więc moje pytanie brzmi: jaka jest klasyfikacja złożoności (jeśli w ogóle) w teorii portfela Markowitza w ogóle, …
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.