Teoretyczne informatyka

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

1
Gdzie jest usterka w metodzie Bluma-Feldmana-Micali
Blum, Micali i Feldman (BFM) przedstawiają nowy (kryptograficzny) model, w którym wszystkie strony (uczciwe lub przeciwne) mają dostęp do niektórych ciągów znaków. Zakłada się, że ciąg jest wybrany zgodnie z pewną dystrybucją (zwykle równomierną dystrybucją) przez zaufaną stronę. Nazywa się to ciągiem odniesienia , a model jest trafnie nazwany modelem …
3
Twardość UGC predykatu
Tło : W oryginalnym dokumencie UGC Subhash Khota ( PDF ) udowadnia trudność UG w podejmowaniu decyzji, czy dana instancja CSP z ograniczeniami w całej formie Niezupełna (a, b, c) w stosunku do trójskładnikowego alfabetu przyznaje zadanie spełniające 1 - ograniczeń lub czy nie ma zadowalających zadań 8ϵϵ\epsilonograniczeń, dla dowolnie …
1
Czy możemy zdecydować, czy stały ma unikalny termin?
Załóżmy, że otrzymujemy macierz n przez n, M, z wpisami liczb całkowitych. Czy możemy zdecydować w P, czy istnieje permutacjaσσ\sigma taka, że ​​dla wszystkich permutacji mamy ?π≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Õ Mi π( i )ΠM.jaσ(ja)≠ΠM.jaπ(ja)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Uwagi Oczywiście można wymienić produkt na sumę, problem pozostaje ten …
1
Języki kompletne i wrażliwe na kontekst.
Interesują mnie dwa pytania dotyczące języków kontekstowych (CSL) i kompletności: Czy istnieje pojęcie kompletności CSL i które języki są kompletne? Czy istnieją naturalne CSL, które są NP-kompletne? W przypadku 2. z pewnością mogę myśleć o naturalnych językach NP-zupełnych, które są CSL (ponieważ CSL jest równy NSPACE [nnn ], SAT to …
5
Silniejsze pojęcia ujednolicenia?
Jedną z luk, o której zawsze zdawałem sobie sprawę, że tak naprawdę nie rozumiem, jest między niejednorodną i jednolitą złożonością obliczeniową, gdzie złożoność obwodu reprezentuje niejednorodną wersję, a maszyny Turinga to, że rzeczy są jednolite. Przypuszczam, że „jednolity” jest sposobem na ograniczenie klasy algorytmów, np. Niedopuszczenie zupełnie innego obwodu dla …
3
Które problemy
Słynny obraz świata Neila Immermana jest następujący (kliknij, aby powiększyć): Jego „Naprawdę wykonalna” klasa nie obejmuje żadnej innej klasy; moje pytanie brzmi: Co to jest problem AC 0, który jest uważany za niepraktyczny i dlaczego?
1
Bardziej wydajna nierównomierna derandomizacja?
Adleman, FOCS'78 wykazał, że dowolny randomizowany obwód dla wejść o długości może być nierównomiernie derandomizowany. Jednak konstrukcja skutecznie powiela pierwotny obwód razy, więc obwód derandomizowany jest większy niż obwód pierwotny o współczynnik . Czy istnieje bardziej wydajna konstrukcja, która zwielokrotnia rozmiar obwodu przez mniejszy współczynnik?nnnO ( n )O(n)O(n)O ( n …
1
Czułość właściwości wykresu
W [1] Turan pokazuje, że czułość (zwana w dokumencie „złożonością krytyczną”) właściwości wykresu jest ściśle większa niż ⌊ 14m ⌋⌊14m⌋\lfloor {1\over 4} m \rfloorgdziemmmjest liczbą wierzchołków na wykresie. Dalej zakłada, że ​​każda nietrywialna właściwość graficzna ma czułość≥m−1≥m-1\geq m-1. Wspomina, że ​​zostało to zweryfikowane dla. Czy poczyniono jakieś postępy w tej …
1
Rozszerzenia beta-teorii rachunku lambda
Beta-eta-teoria rachunku lambda jest ukończona. Czy można dodać dodatkowe reguły, aby rozszerzyć teorię beta rachunku lambda, aby uzyskać teorie zbieżne inne niż teoria beta-eta? Postscriptum To pytanie naruszyło moją zasadę, że pytania powinny wyjaśniać, dlaczego pytający się przejmuje. Pewnej nocy uderzyło mnie niedługo, zanim ta strona przeszła na prywatną wersję …
3
Czy niedeterministyczne skończone automaty (NDFA) można skutecznie konwertować na deterministyczne skończone automaty (DFA) w podwykładniczej przestrzeni / czasie?
Dwadzieścia lat temu zbudowałem pakiet wyrażeń regularnych, który obejmował konwersje wyrażeń regularnych na maszynę skończoną (DFA) i obsługiwał wiele zamkniętych operacji wyrażeń regularnych (gwiazda Kleene, konkatenacja, operacje odwrotne, ustawianie itp.). Nie byłem pewien co do najgorszej wydajności mojego pakietu. DFA ma taką samą moc ekspresyjną jak NDFA, ponieważ NDFA w …
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.