Teoretyczne informatyka

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

2
Motywację do stosowania Karp-redukcji w teorii
Pojęcie wielomianowych redukcji czasu (redukcje Cooka) jest abstrakcją bardzo intuicyjnej koncepcji: skutecznego rozwiązywania problemu za pomocą algorytmu dla innego problemu. Jednakże, w teorii -completeness pojęcie -hardness jest rejestrowany za pomocą redukcji odwzorowania (redukcje Karp). Ta koncepcja „ograniczonych” redukcji jest o wiele mniej intuicyjna (przynajmniej dla mnie). Wydaje się nawet nieco …
3
podświetlany i polaryzujący typy Pi
W ostatnim wątku na liście mailingowej Agdy pojawiło się pytanie o prawa ηη\eta , w których Peter Hancock wypowiedział się prowokująco . Rozumiem, że prawa ηη\eta mają typy negatywne, tj. łączniki, których zasady wprowadzania są odwracalne. Aby wyłączyć ηη\eta dla funkcji, Hank sugeruje użycie niestandardowego eliminatora, funsplit , zamiast zwykłej …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
2
Czy można zdecydować równoważność w Systemie F (lub innym typowym rachunku λ)?
Wiem, że nie można zdecydować równoważności dla niepoprawnego rachunku lambda. Cytując Barendregt, HP Rachunek lambda: jego składnia i semantyka. Północna Holandia, Amsterdam (1984). :ββ\beta Jeśli A i B są rozłączne, niepuste zbiory terminów lambda, które są zamknięte na zasadzie równości, to A i B są rekurencyjnie nierozdzielne. Wynika z tego, …
3
Reguła ramki jako preserver zmian?
Reguła rama , jak ten podany poniżej, oddaje ideę, że, biorąc pod uwagę program cz warunkiem p, że posiada zanim skończy i postcondition qktóra posiada potem jakiś warunek rozłączne rpowinny utrzymać zarówno przed jak i po cserii. ( *Łącznik wymaga, aby jego argumenty były rozłączne.) Często warunki wstępne i końcowe …
2
Czy istnieje teoria łącząca teorię kategorii / algebrę abstrakcyjną i złożoność obliczeniową?
Teoria kategorii i algebra abstrakcyjna zajmują się sposobem łączenia funkcji z innymi funkcjami. Teoria złożoności dotyczy tego, jak trudna jest funkcja do obliczenia. Dziwne jest dla mnie to, że nie widziałem, aby ktoś łączył te kierunki studiów, ponieważ wydają się one takimi naturalnymi parami. Czy ktoś już to zrobił? Jako …
2
Jak ciężka jest mafia?
Mafia to popularna gra fabularna na imprezach, szczegółowy opis jest dostępny na stronie wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 . Zasadniczo działa w następujący sposób: Na początku każdemu z graczy potajemnie przypisywana jest rola, dostosowana do mafii lub miasta. Każda rola może mieć specjalne umiejętności; więcej o tym później.N.N.N Istnieją dwie fazy gry: dzień …
1
Jaka jest złożoność liczenia losowego 2-SAT?
Czy podjęto prace nad tym, jak złożoność przypadkowych instancji # 2-SAT zmienia się w zależności od gęstości klauzuli? To znaczy: w jaki sposób trudność liczenia satysfakcjonujących rozwiązań dla losowo generowanej instancji 2-SAT różni się w zależności od gęstości klauzuli? W szczególności, czy znane są rygorystyczne wyniki dotyczące progów krytycznych? Oczywiście, …
3
Dlaczego używamy maszyn Turinga z pojedynczą taśmą ze względu na złożoność czasu?
Jak wiadomo, istnieje wiele anomolii w maszynach Turinga z pojedynczą taśmą, gdy czas jest o(n2)o(n2)o(n^2) : symulacja wielopasmowa TM, symulacja większego alfabetu taśmy za pomocą tylko {0,1,b}{0,1,b}\{0,1,b\} , konstruowania czasu, nieszczelności twierdzenia o hierarchii czasu, ... Również wyniki, takie jak DTime(o(nlgn)=RegDTime(o(nlg⁡n)=Reg\mathsf{DTime}(o(n\lg n)=\mathsf{Reg} , i bardzo specyficzne dla modelu dolne granice …
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.