Teoretyczne informatyka

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

2
Kompletność obejmująca drzewa
Drzewo opinające wykresu nazywane jest drzewem kompletności, jeśli zbiór jego liści indukuje całkowity podrozdział na grafie gospodarza. Biorąc pod uwagę wykres i liczbę całkowitą , jaka jest złożoność decyzji, czy zawiera drzewo kompletności z co najwyżej liści?GsolGkkkGGGkkk Powodem zadawania tego pytania jest to, że odpowiadającym problemem dla drzew niezależności jest …
2
Sformalizowanie teorii zbiorów skończonych w teorii typów
Większość asystentów dowodowych ma sformalizowaną koncepcję „zbioru skończonego”. Te formalizacje różnią się jednak bardzo dziko (choć można mieć nadzieję, że wszystkie są w zasadzie równoważne!). Nie rozumiem w tym momencie zajmowanej przestrzeni projektowej oraz jakie są zalety i wady każdej formalizacji. W szczególności chciałbym zrozumieć, co następuje: Czy mogę aksjatyzować …
2
Twardość podtytuły Zestawu okładki
Jak trudny jest problem Ustaw okładkę, jeśli liczba elementów jest ograniczona przez jakąś funkcję (np. ), gdzie jest rozmiarem wystąpienia problemu. Formalnie,nlognlog⁡n\log nnnn Niech i gdzie i . Jak trudno jest rozwiązać następujący problemF = { S 1 , ⋯ , S n } S i ⊆ U m = …
1
,
Próbowałem zrozumieć te zajęcia, ale zawsze byłem zdezorientowany ... pytania są następujące: Jaki jest związek między a # P , w szczególności czy jest to pytanie otwarte?faN.P.faN.P.FNP# P#P.\#P Jaki jest stosunek i N P ? czy to pytanie jest otwarte?⊕ P.⊕P.\oplus PN.P.N.P.NP A co z relacją między a P F …
1
Liczby całkowite wielomianu
Jakiego algorytmu możemy użyć do znalezienia wszystkich pierwiastków całkowitych wielomianu o współczynnikach całkowitych?fa( x )f(x)f(x) Zauważyłem, że Sage może znaleźć pierwiastki w ciągu kilku sekund, nawet jeśli wszystkie współczynniki są bardzo duże. Jak to zrobić?fa( x )f(x)f(x)
1
Naturalny problem w
Klasa złożoności jest zdefiniowana następująco (z Wikipedii ):SP2S.2)P.\textrm{S}_2^\textrm{P} Język znajduje się w S P 2, jeśli istnieje predykat P wielomianowy taki, żeLL.LSP2S.2)P.S_2^PPP.P Jeśli , to istnieje y takie, że dla wszystkich z , P ( x , y , z ) = 1x ∈ L.x∈L.x \in LyyyzzzP.( x , y, …
4
Prosty przypadek SAT, który nie jest łatwy do rozpoznania drzewa
Czy istnieje naturalna klasa formuł CNF - najlepiej taka, która była wcześniej badana w literaturze - o następujących właściwościach:doCC jest łatwym przypadkiem SAT, takim jak np. Horn lub 2-CNF, tj. Członkostwo w C można badać w czasie wielomianowym, a wzory F ∈ C można badać pod kątem satysfakcji w czasie …
1
Dowody w
W przemówieniu Razborowa opublikowano dziwne oświadczenie. Jeśli FACTORING jest trudny, to małe twierdzenie Fermata nie jest możliwe do udowodnienia w S12S21S_{2}^{1} . Co to jest S12S21S_{2}^{1} i dlaczego aktualnych dowodów nie ma w S12S21S_{2}^{1} ?
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.