Istnieją pewne problemy z liczeniem, które polegają na zliczaniu wykładniczo wielu rzeczy (w stosunku do wielkości danych wejściowych), a jednak mają zaskakujące algorytmy deterministyczne o czasie wielomianowym. Przykłady obejmują: Zliczanie idealnych dopasowań na wykresie planarnym ( algorytm...
To moje pierwsze pytanie na tej stronie. Biorę kurs magisterski z teorii obliczeń. Jak wytłumaczysz problem P = NP 10-letniemu dziecku i dlaczego ma on taką nagrodę pieniężną? Twoje zdanie? Zaktualizuję pytanie, gdy moja głowa się o tym
W złożoności opisowej Immerman ma Wniosek 7.23. Następujące warunki są równoważne: 1. P = NP. 2. Przekroczone, uporządkowane struktury, FO (LFP) = SO. Można to uznać za „wzmocnienie” P = NP do równoważnego wyrażenia w (przypuszczalnie) większych klasach złożoności. Zauważ, że SO...
Wielu wybitnych informatyków i grup badawczych prowadzi aktywne blogi, które informują nas o najnowszych badaniach w zakresie zainteresowań autorów. W większości przypadków posty na blogu są łatwiejsze do zrozumienia niż oficjalne dokumenty, ponieważ pomijają większość krwawych szczegółów...
Załóżmy, że i G 2 to dwa niekierowane wykresy na zbiorze wierzchołków { 1 , … , n } . Wykresy są izomorficzne wtedy i tylko wtedy, gdy występuje permutacja Π taka, że G 1 = Π ( G 2 ) lub bardziej formalnie, jeśli istnieje permutacja Π taka, że ( i , j ) jest krawędzią w G 1 wtedy i tylko if ( Π ( i...
Mój doktorat jest w czystej matematyce i przyznaję, że niewiele wiem (tj. nic) na temat teoretycznej CS. Jednak zacząłem badać opcje pozaakademickie w mojej karierze i zapoznałem się z uczeniem maszynowym, natknąłem się na takie stwierdzenia, jak: „Nikt nie rozumie, dlaczego sieci neuronowe...
Rozważ rozłącznych rodzin podzbiorów {1,2,…, n}, F 1 , F 2 , … F t .tttfa1, F.2), … FtF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Przypuszczam, że (*) Dla każdego i każdy R ∈ F ı i T ∈ K K , jest S ∈ F j , który zawiera R ∩ T .i < j < ki<j<ki \lt j \lt kR ∈ FjaR∈FiR \in {\cal...
Istnieją dwa sposoby analizy wydajności algorytmu nałożyć asymptotyczną górną granicę czasu działania, oraz aby go uruchomić i zebrać dane eksperymentalne. Zastanawiam się, czy są znane przypadki, w których istnieje znaczna różnica między (1) a (2). Rozumiem przez to, że albo (a) dane...
W przypadku (wyszukiwania wersji) problemów z NP zakończonych weryfikacja rozwiązania jest wyraźnie łatwiejsza niż znalezienie, ponieważ weryfikacja może być przeprowadzona w czasie wielomianowym, podczas gdy znalezienie świadka zajmuje (prawdopodobnie) wykładniczy czas. Jednak w P rozwiązanie...
To pytanie jest inspirowane innym pytaniem o to, co nowego w PFDS od publikacji książki Okasaki w 1998 roku . Zacznę od dwóch pytań, które mam: Czy istnieje czysto funkcjonalna struktura danych, która zbliża się do prędkości tabel mieszania? Prób jeszcze tam nie ma. Czy istnieją czysto...
Często jestem pytany, co robi teoretyczny informatyk. Byłoby wspaniale mieć kilka miłych odpowiedzi na to pytanie. Zwykle wracam do technicznego żargonu, a oczy ludzi zwykle w tym momencie się błyszczą. Co robi teoretyczny informatyk w kategoriach zrozumiałych dla osób niebędących...
Po owocnym pytaniu w MO pomyślałem, że warto przedyskutować kilka znaczących nazw artykułów w CS. Oczywiste jest, że większość z nas może być zainteresowana przeczytaniem (lub przynajmniej spojrzeniem) artykułu o interesującym tytule (przynajmniej robię to za każdym razem, gdy przeglądam listę...
W swoim słynnym artykule „Conjugate Coding” (napisanym około 1970 r.) Stephen Wiesner zaproponował schemat pieniądza kwantowego, który jest bezwarunkowo niemożliwy do sfałszowania, zakładając, że bank emitujący ma dostęp do ogromnej tabeli liczb losowych i że banknoty można przynieść z powrotem do...
Czy istnieje związek między Maszyną Turinga a rachunkiem lambda - czy zdarzyło się, że powstały mniej więcej w tym samym
To może być pytanie subiektywne, a nie konkretne, ale tak czy inaczej. W teorii złożoności badamy pojęcie wydajnych obliczeń. Istnieją klasy takie jak oznacza czas wielomianowy , a L oznacza miejsce na log . Oba są uważane za reprezentowane jako rodzaj „wydajności” i dość dobrze wychwytują...
Mam trzy powiązane pytania, które są zaznaczone punktorami poniżej (nie, nie można ich podzielić, jeśli się zastanawiasz). Andrej Bauer napisał tutaj , że niektóre funkcje można realizować za pomocą maszyny Turinga, ale nie za pomocą rachunku lambda. Kluczowym krokiem jego rozumowania jest:...
Programowanie funkcjonalne ma teoretyczne podstawy w rachunku lambda i logice kombinatorycznej . Jako osoba zajmująca się obliczeniami statystycznymi uważam te koncepcje za bardzo przydatne do modelowania. Czy istnieje równoważna matematyczna podstawa programowania imperatywnego , czy może po...
Niektóre problemy są nierozstrzygalne, ale mimo to można poczynić pewne postępy w ich rozwiązywaniu. Na przykład problem zatrzymania jest nierozstrzygalny, ale można poczynić praktyczne postępy w tworzeniu narzędzi do wykrywania potencjalnych nieskończonych pętli w kodzie. Problemy z układaniem...
Kilka problemów optymalizacyjnych, o których wiadomo, że są trudne do NP na grafach ogólnych, można w prosty sposób rozwiązać w czasie wielomianowym (niektóre nawet w czasie liniowym), gdy grafem wejściowym jest drzewo. Przykłady obejmują minimalną osłonę wierzchołków, maksymalny niezależny zestaw,...
Podczas kodowania logiki w asystencie dowodu, takim jak Coq lub Isabelle, należy dokonać wyboru między użyciem płytkiego a głębokiego osadzenia. W płytkim osadzaniu formuły logiczne są zapisywane bezpośrednio w logice twierdzenia twierdzącego, podczas gdy w głębokim osadzaniu formuły logiczne są...