Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

4
Chaos i pytanie
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 ograniczeń”. Nature Physics 7, no. 12 (2011): 966–970. ( Link do czasopisma ). Czy …
2
Dowód, że górne granice obwodu dla
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 , B n …
2
Złożoność odzyskiwania macierzy sąsiedztwa z jej kwadratu
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 jako problem wyszukiwania, w którym podane są macierzy do A …
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 …
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 …
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 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.