Teoretyczne informatyka

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

1
Tardos Funkcja kontrprzykład do Bluma
W tym wątku próba próby Norbet Bluma jest zwięźle obalona przez odnotowanie, że funkcja Tardos jest przeciwne do Twierdzenia 6.P.≠ N.P.P≠NPP \neq NP Twierdzenie 6 : Niech będzie dowolną monotoniczną funkcją boolowską. Załóżmy, że istnieje aproksymator A CNF-DNF, którego można użyć do udowodnienia dolnej granicy C m ( f ) …
3
Czy istnieje wynik w teorii obliczalności, która nie jest relatywizowana?
Czytałem artykuł Andreja Bauera Pierwsze kroki w teorii obliczeń syntetycznych . Na zakończenie zauważa to Nasza aksjatyzacja ma swoje granice: nie może udowodnić żadnych wyników w teorii obliczeń, które nie relatywizują się do obliczeń wyroczni. Jest tak, ponieważ teorię można interpretować jako wariant efektywnego toposu zbudowanego z częściowych funkcji rekurencyjnych …
2
Jaki był pierwotny zamiar stworzenia rachunku Lambda?
Czytałem, że początkowo Kościół zaproponował -calculus jako część swoich postulatów z logiki (co jest gęstym odczytem). Ale Kleene udowodnił, że jego „system” jest niespójny, po czym Church wyodrębnił odpowiednie rzeczy do swojej pracy nad „skutecznym obliczeniem” i porzucił wcześniejsze prace nad logiką.λλ\lambda Tak jak ja rozumiem, -system i jego oznaczenia …
2
Najlepsza bieżąca dolna granica dla SAT?
Kontynuując poprzednie pytanie , jakie są najlepsze obecne dolne granice przestrzeni dla SAT? Przez spację dolną rozumiem tutaj liczbę komórek taśmy roboczej używanych przez maszynę Turinga, która używa binarnego alfabetu taśmy roboczej. Stały składnik addytywny jest nieunikniony, ponieważ TM może wykorzystywać stany wewnętrzne do symulacji dowolnej stałej liczby komórek taśmy …
5
Ciekawy o komputerowych dowodach kompletności NP
W artykule „KOMPLEKSOWOŚĆ PROBLEMÓW Z ZADOWOLENIEM” Tomasza J. Schaefera autor wspomniał, że This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity could be explored with the help of a computer. The computer would be …
1
Jakie są praktyczne problemy z typami skrzyżowań i złączy?
Projektuję prosty funkcjonalny język programowania o typie statycznym jako sposób uczenia się. Wygląda na to, że system typów, który do tej pory wdrożyłem, może (przy odrobinie dodatkowej pracy) zawierać typy skrzyżowań i złączy, np. Możesz mieć: <Union String Integer> <Union Integer Foo> Przecięcie dwóch powyższych typów byłoby równiną Integer Połączenie …
1
Dokładnie płaski przepływ elektryczny
Rozważmy sieć elektryczną zamodelowaną jako płaski wykres G, gdzie każda krawędź reprezentuje rezystor 1 Ω. Jak szybko możemy obliczyć dokładną efektywną rezystancję między dwoma wierzchołkami w G? Równolegle, jak szybko możemy obliczyć dokładny prąd płynący wzdłuż każdej krawędzi, jeśli podłączymy baterię 1 V do dwóch wierzchołków w G? Znane prawa …
10
Problemy łatwe w przypadku wykresów nieważonych, ale trudne w przypadku wykresów ważonych
Wiele problemów związanych z grafem algorytmicznym można rozwiązać w czasie wielomianowym zarówno na wykresach nieważonych, jak i ważonych. Niektóre przykłady to najkrótsza ścieżka, min. Drzewo rozpinające, najdłuższa ścieżka (w ukierunkowanych grafach acyklicznych), maksymalny przepływ, min. Cięcie, maks. Dopasowanie, optymalne arborescencje, niektóre najgęstsze problemy z podgrafami, maks. Rozłączne nacięcia ukierunkowane, maks. …
3
Uzasadnianie naukowcom asymptotycznej analizy najgorszego przypadku
Pracowałem nad wprowadzeniem niektórych wyników złożoności obliczeniowej do biologii teoretycznej, zwłaszcza ewolucji i ekologii , aby być interesującym / użytecznym dla biologów. Jedną z największych trudności, jakie napotkałem, jest uzasadnienie przydatności asymptotycznej analizy najgorszego przypadku dla dolnych granic. Czy istnieją odniesienia do długości artykułów, które uzasadniają dolne granice i asymptotyczną …
2
Wykresy, na których wszystkie najkrótsze ścieżki są unikalne
Szukam nieukierunkowanych, nieważonych połączonych wykresów , w których dla każdej pary u , v ∈ V istnieje unikalna ścieżka u → v, która realizuje odległość d ( u , v ) .G = ( V, E)sol=(V.,mi)G=(V,E)u , v ∈ V.u,v∈V.u,v \in Vu → vu→vu \rightarrow vre( u , v )re(u,v)d(u,v) …
2
Dolna granica wyznacznika i wartości stałej
W świetle niedawnej otchłani na głębokości 3 wynik (który między innymi daje głębokości 3 arytmetyczna obieg donxndeterminant naC) I mają następujące pytania: Grigoriev i Karpińskiokazałosię2omów(n)dolna granica dla każdego arytmetyczna obwodu głębokości-3 obliczeniowej wyznacznikanxnmacierze nad polami skończonymi (które, jak sądzę, dotyczą również Stałych). Wzór Ryserana obliczenie Stałego daje obwód arytmetyczny o …
1
Czy istnieje problem, który jest łatwy w przypadku wykresu sześciennego, ale trudny w przypadku wykresów o maksymalnym stopniu 3?
Wykresy sześcienne to wykresy, w których każdy wierzchołek ma stopień 3. Zostały one szeroko zbadane i jestem świadomy, że kilka problemów trudnych dla NP pozostaje trudnych dla NP nawet ograniczonych do podklas grafów sześciennych, ale niektóre inne stają się łatwiejsze. Nadklasą wykresów sześciennych jest klasa grafów o maksymalnym stopniu .Æ …
1
Klasyfikacja bram dwustronnych
Krata Posta , opisana przez Emila Posta w 1941 r., Jest w zasadzie kompletnym diagramem włączenia zestawów funkcji boolowskich, które są zamknięte w składzie: na przykład funkcje monotoniczne, funkcje liniowe nad GF (2) i wszystkie funkcje. (Post nie zakładał, że stałe 0 i 1 są dostępne za darmo, co znacznie …
9
Zwięzłe wprowadzenie do algorytmów dla matematyków
Szukam zwięzłego tekstu wprowadzającego na temat algorytmów z omówioną teorią wysokiego współczynnikatheory coveredtotal number of pages.theory coveredtotal number of pages.\frac{\mbox{theory covered}}{\mbox{total number of pages}}.Powinno zacząć się od początku, ale potem szybko postępować, nie poświęcając zbyt wiele czasu na przykłady z prawdziwego świata, elementarne techniki dowodowe itp. Jako matematyk badawczy mam …
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.