Teoretyczne informatyka

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

3
Co odróżnia łatwe globalne problemy od twardych globalnych problemów na wykresach ograniczonej szerokości?
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 zweryfikować, badając niewielkie sąsiedztwo każdego wierzchołka. Co ciekawe, nawet problemy (takie jak ścieżka …
2
Dlaczego nieskończona hierarchia typów?
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 {} {∅ ⊢ * : ◽} Γ⊢T1:s1Γ,x:T1⊢t:T2Γ⊢(λx:T1,t):(Πx:T1,T2)Γ⊢T1:s1Γ,x:T1⊢t:T2Γ⊢(λx:T1,t):(Πx:T1,T2)\frac {Γ …
2
Problemy z wydajnym rozwiązaniem, z wyjątkiem niewielkiej części nakładów
Problemem zatrzymania maszyn Turinga jest być może kanoniczny nierozstrzygalny zestaw. Niemniej jednak dowodzimy, że istnieje algorytm decydujący o prawie wszystkich jego wystąpieniach. Problem zatrzymania należy zatem do rosnącej liczby osób wykazujących zjawisko teorii złożoności „czarnej dziury”, w którym trudność niewykonalnego lub nierozstrzygalnego problemu ogranicza się do bardzo małego regionu, czarnej …
5
Jakie znaczące modele automatów mają wielomianowo rozstrzygalne ograniczenie?
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 ( M2))L.(M.1)⊆L.(M.2))L(M_1) \subseteq L(M_2) Oczywiste, które przychodzą na myśl, …
2
Rozwiązane w czasie wielomianowe wystąpienia Max-Sat
Problem Max-Sat prosi o znalezienie przypisania formuły CNF, która spełnia jak najwięcej klauzul. Dla prostszego problemu SAT istnieje wiele znanych specjalnych przypadków, które można rozwiązać w czasie wielomianowym, np. Możemy rozwiązać 2-SAT w czasie wielomianowym. W przypadku Max-Sat sytuacja jest inna, ponieważ Max-Sat jest trudny dla NP nawet dla formuł …
18 sat  treewidth  max2sat 
2
Co-NP-kompletność minimalnej trasy TSP?
Ten problem pojawił się w moim niedawnym poście na blogu , przypuśćmy, że masz wycieczkę po TSP, czy jest to zgodne z NP-kompletnym, aby ustalić, czy jest to minimalne? Dokładniej jest następujący problem NP-zupełny: Instancja: Biorąc pod uwagę pełny wykres G z krawędziami ważonymi dodatnimi liczbami całkowitymi i prosty cykl …
4
Otwarte problemy związane z izomorfizmem grafowym
Obecnie prowadzę przegląd literatury dotyczący problemu izomorfizmu grafowego (GI). Chciałbym poznać kilka otwartych pytań związanych z następującymi zagadnieniami Jakie są parametry wykresu, dla których ustalona zdolność pomiarowa GI jest otwartym problemem. Jakie są parametry wykresu, przez ustalenie ich wielomianowej zdolności do rozwiązywania GI nie jest znana. Złożoność GI, gdy jest …
5
Algorytmy szybkiej prędkości
Chciałbym obliczyć szerokość wykresu. Istnieją naprawdę dobre heurystyki dla innych problemów związanych z grafem NP-twardym, takich jak VF2 dla izomorfizmu podgraficznego , z kodem dostępnym na przykład w igraph . Wypróbowałem je na moich wykresach i okazało się, że działają bardzo szybko dla moich danych. Czy są jakieś szybkie algorytmy …
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.