Coq, Agda i Idris mają nieskończoną hierarchię typów (Typ 1: Typ 2: Typ 3: ...). Ale dlaczego nie zrobić tego zamiast λC, układu w sześcianie lambda najbliższego rachunku różniczkowego konstrukcji, który ma tylko dwa rodzaje, i ◽ , i te reguły?∗∗*◽◽◽ ∅⊢∗:◽∅⊢∗:◽\frac {} {∅ ⊢ * :...
Próbuję rozwiązać konkretny problem i pomyślałem, że mogę go rozwiązać za pomocą teorii automatów. Zastanawiam się, jakie modele automatów mają rozstrzygające rozstrzyganie w czasie wielomianowym? tzn. jeśli masz maszyny M.1, M2)M.1,M.2)M_1, M_2 , możesz sprawdzić, czy wydajnie.L ( M1) ⊆ L (...
Wiele trudnych problemów graficznych można rozwiązać w czasie wielomianowym na wykresach ograniczonej szerokości . Rzeczywiście, podręczniki zwykle używają np. Zestawu niezależnego jako przykładu, co jest problemem lokalnym . Z grubsza problem lokalny to problem, którego rozwiązanie można...
Cóż, tytuł prawie wszystko mówi. Interesujące pytanie powyżej zostało zadane przez komentatora Jaya na moim blogu (patrz tutaj i tutaj ). Zgaduję, że odpowiedź brzmi „tak” i że istnieje stosunkowo prosty dowód, ale nie widziałem go od razu. (Jednak z grubsza można by próbować pokazać, że jeśli...
Chciałbym wiedzieć, czy w TCS istniały przypuszczenia, które od dawna nie zostały udowodnione, a które później udowodniono na podstawie innego twierdzenia, które mogłyby być łatwiejsze do udowodnienia.
Treewidth odgrywa ważną rolę w algorytmach FPT, częściowo dlatego, że wiele problemów jest FPT parametryzowanych przez treewidth. Powiązanym, bardziej ograniczonym pojęciem jest szerokość ścieżki. Jeśli wykres ma szerokość ścieżki , ma również szerokość co najwyżej , podczas gdy w kierunku...
Interesuje mnie następujący problem: Biorąc pod uwagę macierz , czy istnieje niekierowany wykres na n wierzchołkach, których macierz przylegania do kwadratu jest tą macierzą?n × nn×nn\times nnnn Czy znana jest złożoność obliczeniowa tego problemu? Uwagi: Oczywiście może być również sformułowany...
W oficjalnym opisie problemu Clay dla P kontra NP stwierdzono, że wynikałoby z pokazania, że „każdy język w E [klasa języków rozpoznawalnych w czasie wykładniczym z deterministyczną maszyną Turinga] może być obliczony przez rodzinę obwodów boolowskich < B n > , tak że co najmniej jedno n ,...
Interesuje mnie nauka powiązań między „chaosem”, a szerzej, systemami dynamicznymi, a pytaniem . Oto przykład rodzaju literatury, której szukam:P.= NP.P.=N.P.P{=}NP Ercsey-Ravasz, Mária i Zoltán Toroczkai. „Twardość optymalizacji jako przejściowy chaos w analogicznym podejściu do satysfakcji z...
To dobrze znany wynik, że pytanie Czy gramatyka bezkontekstowa generuje zwykły język? jest nierozstrzygalny. Jednak staje się to rozstrzygalne na podstawie jednoznacznego alfabetu, po prostu dlatego, że w tym przypadku klasy języków bezkontekstowych i zwykłych pokrywają się. Moje pytanie...
Czy są jakieś NP całkowite problemy bez nieskończonego podzbioru instancji ΦΦ\Phi takie, że członkostwo w ΦΦ\Phi można ustalić w czasie wielomianowym, a dla wszystkich x ∈ Φx∈Φx \in \Phi , xxx można rozwiązać w czasie wielomianowym? (Zakładając P.≠ N.P.P.≠N.P.P \neq NP...
Czy jest jakiś realizowany projekt formalnej weryfikacji twierdzeń i dowodów teorii złożoności przy użyciu asystenta dowodu, takiego jak Coq? Czy są jakieś
Rozwiązuję problem, który w innym miejscu jest trudny do NP, powiedzmy w artykule [XYZ]. Twardość NP podana w [XYZ] jest skomplikowana i wykorzystuje zaawansowane techniki. Po kilku badaniach i pracach udało mi się dać prosty i jasny dowód na twardość NP. Zastanawiam się, czy jest to uważane za...
Czy istnieje znany, wyraźny przykład algorytmu o takiej właściwości, że jeśli to ten algorytm nie działa w czasie wielomianowym, a jeśli to działa w czasie wielomianowym?P≠NPP≠NPP\neq
Zdaję sobie sprawę, że może to być kontrowersyjne pytanie, ale wydawało się, że to właściwe miejsce do zadawania pytań. Proszę mnie przekierować, jeśli nie. Tło jest takie, że jestem „praktykiem” (doktorantem, nie studiuję teorii CS), ale mam uzasadnione podstawy w algorytmach licencjackich i...
Obliczenia kwantowe to aktywny obszar badań, który ma na celu wykorzystanie fizyki kwantowej (np. Splątanie kwantowe) w celu zwiększenia wydajności komputerów (nie zmienia tezy Kościoła-Turinga ). Jakie są najbardziej znaczące eksperymenty przeprowadzone w celu zademonstrowania teorii obliczeń...
Załóżmy, że otrzymałeś połączony, prosty, niekierowany wykres H. Problem cięcia bez H jest zdefiniowany następująco: Biorąc pod uwagę prosty, nieukierowany wykres G, istnieje cięcie (podział wierzchołków na dwa niepuste zbiory, L, R), tak że oba wykresy indukowane przez zestawy cięcia (L i R)...
Zwykle wydajne algorytmy mają wielomianowe środowisko wykonawcze i wykładniczo dużą przestrzeń rozwiązania. Oznacza to, że problem musi być łatwy w dwóch aspektach: po pierwsze, problem można rozwiązać w wielomianowej liczbie kroków, a po drugie, przestrzeń rozwiązania musi być bardzo...
Powszechnie wiadomo, że zestawem języków posiadających dwuczłonowy interaktywny system proof, w którym weryfikator działa w czasie wielomianowym (MIP), jest NEXP. Ale czy znane są granice mocy takich interaktywnych dowodów, gdy dowody mają ograniczoną moc? Na przykład, jaka jest klasa języków,...
Dynamika Glaubera to łańcuch Markowa na kolorach wykresu, w którym na każdym kroku próbuje się pokolorować losowo wybrany wierzchołek o losowym kolorze. Nie miesza się w przypadku 3 kolorów w 5 cyklach: istnieje 30 3 kolorów, ale tylko 15 z nich można osiągnąć za pomocą etapów kolorowania...