Teoretyczne informatyka

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

1
Dobre referencje na temat przybliżonych metod rozwiązywania problemów logicznych
Wiadomo, że wiele problemów logicznych (np. Problemy satysfakcji kilku logik modalnych) nie są rozstrzygalne. Istnieje również wiele nierozstrzygalnych problemów w teorii algorytmów, np. W optymalizacji kombinatorycznej. Ale w praktyce heurystyki i algorytmy przybliżone działają dobrze w przypadku algorytmów praktycznych. Można więc oczekiwać, że odpowiednie będą również algorytmy przybliżone dla problemów …
1
Jaka jest złożoność sprawdzenia, czy macierz można diagonalizować?
Biorąc pod uwagę macierzy A z racjonalnym pozycji. Jaką złożoność sprawdzenia A można diagonalizować?n×nn×nn\times nAAAAAA Podejrzewam, że można to zrobić w P, ale nie znam żadnego odniesienia. Bardziej interesujące jest jednak pytanie, czy istnieje jakaś lepsza klasa złożoności, aby uchwycić ten problem? Wszelkie wskazówki / komentarze są mile widziane! Dzięki.
1
Odległość między zwykłymi językami
Chcę zdefiniować pojęcie „bliskości” między dwoma regularnymi językami skończonych słów w (i / lub nieskończonych słów w Σ ω ). Podstawową ideą jest to, że chcemy, aby dwa języki były blisko siebie, jeśli nie różnią się wieloma słowami. Możemy również w jakiś sposób wykorzystać odległość edycji ... Nie mogłem znaleźć …
4
(N) DFA z tymi samymi stanami początkowymi / akceptującymi
Co wiadomo o klasie języków rozpoznawanych przez automaty skończone posiadające ten sam stan początkowy i akceptacji? Jest to właściwy podzbiór zwykłych języków (ponieważ każdy taki język zawiera pusty ciąg znaków), ale jak bardzo jest słaby? Czy istnieje prosta charakterystyka algebraiczna? To samo dotyczy języków rozpoznawanych przez niedeterministyczne automaty posiadające ten …
1
Ile niezależności jest potrzebne do oddzielnego łączenia?
Jeśli kulek zostanie rozmieszczonych losowo w koszach równomiernie, w najbardziej obciążonym pojemniku znajdują się kulki z dużym prawdopodobieństwem. W „The Power of Simple Tabulation Hashing” Pătraşcu i Thorup wspominają, że „Chernoff-Hoeffding ogranicza się do aplikacji o ograniczonej niezależności” ( lustro ) pokazuje, że to ograniczenie populacji najbardziej obciążonego pojemnika utrzymuje …
1
Czy istnieje lista problemów kanonicznych w systemach rozproszonych?
W ubiegłym tygodniu ponownie przeczytałem transkrypt Leslie Lamport z 1982 r. Z konferencji, którą wygłosił na temat Rozwiązanych problemów, Nierozwiązanych problemów i nieproblemów w współbieżności . Artykuł jest czytelny, ale jedną z rzeczy, które skłoniły mnie do myślenia, jest następujące stwierdzenie: Czy każdy problem można uznać za problem wzajemnego wykluczenia …
2
Struktura danych dla aktualizacji interwałów i zapytań o liczbę zer
Szukam struktury danych, która utrzymywałaby tablicę liczb całkowitych o rozmiarze , i pozwalała na następujące operacje w czasie .tttnnnO(logn)O(log⁡n)O(\log n) increase(a,b)increase(a,b)\text{increase}(a,b) , który zwiększa .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b] decrease(a,b)decrease(a,b)\text{decrease}(a,b) , co zmniejsza .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b] support()support()\text{support}() , która zwraca liczbę indeksów takich, że .iiit[i]≠0t[i]≠0t[i]\neq 0 Obiecujesz, że każde połączenie do zmniejszenia można dopasować do poprzedniego …
1
Jak mogę wykorzystać moją teorię obliczeniową i moce analizy dla większego dobra?
Jakie są zastosowania moich „mocy” poza środowiskiem akademickim? Co mogę zrobić poza nauczaniem i publikowaniem artykułów? Gdzie wszystko mogę zastosować swoje uprawnienia? Dla argumentu: proszę założyć, że mam doktorat z algorytmów / TCS i nauczyłem się wielu „rzeczy” i stworzyłem przełomowe granice istniejących algorytmów itp., A także mam solidne podstawy …
2
Edytuj odległość za pomocą operacji przesuwania
Motywacja: Współautor redaguje manuskrypt i chciałbym zobaczyć jasne podsumowanie edycji. Wszystkie narzędzia podobne do „diff” są zwykle bezużyteczne, jeśli zarówno przenosisz tekst (np. Reorganizując strukturę), jak i edytujesz lokalnie. Czy to naprawdę takie trudne? Definicje: Chciałbym znaleźć minimalną odległość edycji, gdzie dozwolone operacje to: „tanie” operacje: dodaj / zmień / …
1
Formuła 3-CNF, która wymaga szerokości rozdzielczości
Przypomnijmy, że szerokość o rozdzielczości odrzucenia o wzorze CNF jest maksymalna liczba literałach w klauzuli występującego w . Dla każdego istnieją niezadowalające wzory w 3-CNF st. Każde odrzucenie rozdzielczości wymaga szerokości co najmniej .F.RRRfaFFw F F wRRRwwwfaFFfaFFwww Potrzebuję konkretnego przykładu niezadowalającej formuły w 3-CNF (tak małej i prostej, jak to …
1
Produkt pośredni
Problem podziału jest słabo NP-zupełny, ponieważ ma wielomianowy (pseudo-wielomianowy) algorytm czasowy, jeśli wejściowe liczby całkowite są ograniczone przez jakiś wielomian. Jednak 3-partycja jest silnym problemem NP-zupełnym, nawet jeśli wejściowe liczby całkowite są ograniczone przez wielomian. Zakładając, , Czy możemy udowodnić, że pośrednie problemy NP-zupełne muszą istnieć? Jeśli odpowiedź brzmi „tak”, …
2
Gra polegająca na ustawianiu nakładających się kręgów, aby zmaksymalizować czas podróży między nimi
Spotkałem następującą grę. Przeprowadzę migrację zgodnie z żądaniem. Błąd odwiedza kręgi, a przeciwnik chce zmaksymalizować swój czas podróży. Przeciwnik umieszcza koło na każdym kroku. Błąd przesuwa się z bieżącej pozycji bezpośrednio w kierunku środka najnowszego kręgu, a następnie zatrzymuje się, gdy napotka wnętrze koła (w ten sposób: nie chodzi, jeśli …
2
Czy istnienie całkowitego problemu wyszukiwania
Łatwo zauważyć, że jeśli to istnieją całkowite N P problemy wyszukiwania, których nie można rozwiązać w czasie wielomianowym (stwórz całkowity problem wyszukiwania, mając zarówno świadków członkostwa, jak i świadków braku członkostwa).N P ∩ c o N P ≠ PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}N P.NP\mathsf{NP} Czy odwrotna jest również prawda, tj Czy istnienie …
1
Dokładne algorytmy dla niewypukłego programowania kwadratowego
To pytanie dotyczy kwadratowych problemów programistycznych z ograniczeniami pudełkowymi (box-QP), tj. Problemów optymalizacyjnych formularza minimalizuj zastrzeżeniem x ∈ [ 0 , 1 ] n .fa( x ) = xT.A x + cT.xf(x)=xTAx+cTxf(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{x}x ∈[0,1 ]nx∈[0,1]n\mathbf{x} \in [0,1]^n Gdyby było pozytywnie półokreślone, wtedy wszystko byłoby …
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.