Pytania otagowane jako complexity-theory

Pytania związane z (obliczeniową) złożonością rozwiązywania problemów

3
Problemy decyzyjne a „rzeczywiste” problemy, które nie są „tak lub nie”
Czytałem w wielu miejscach, że niektóre problemy są trudne do przybliżenia ( NP jest trudne do przybliżenia ). Ale przybliżenie nie jest problemem decyzyjnym: odpowiedź jest liczbą rzeczywistą, a nie Tak lub Nie. Również dla każdego pożądanego współczynnika przybliżenia istnieje wiele odpowiedzi, które są poprawne, a wiele błędnych, a to …
2
Czy istnieje zadanie, które można rozwiązać w czasie wielomianowym, ale którego nie da się zweryfikować w czasie wielomianowym?
Mój kolega i ja właśnie uderzyliśmy w notatki jednego z naszych profesorów. Notatki stwierdzają, że istnieją zadania, które można rozwiązać w czasie wielomianowym (są w klasie PF), ale NIE są możliwe do zweryfikowania w czasie wielomianowym (NIE są w klasie NPF). Aby rozwinąć te klasy: Otrzymujemy trochę danych wejściowych X …
2
Dlaczego uważamy, że PSPACE ≠ EXPTIME?
Mam problem z intuicyjnym zrozumieniem, dlaczego ogólnie uważa się, że PSPACE różni się od EXPTIME. Jeśli PSPACE jest zbiorem problemów możliwych do rozwiązania w wielomianu kosmicznym w wielkości wejściowej fa( n )f(n)f(n) , to w jaki sposób może istnieć klasa problemów, które doświadczają większego wybuchu czasu wykładniczego i nie wykorzystują …
2
NP-Trudne problemy, których nie ma w NP, ale są rozstrzygalne
Zastanawiam się, czy istnieje dobry przykład łatwego do zrozumienia problemu NP-Hard, który nie jest NP-Complete i nie jest nierozstrzygalny? Na przykład problem zatrzymania jest NP-trudny, a nie NP-kompletny, ale jest nierozstrzygalny. Uważam, że oznacza to, że problem można zweryfikować, ale nie w czasie wielomianowym. (Proszę poprawić to oświadczenie, jeśli tak …
4
Jak mogę zweryfikować rozwiązanie problemu Traveling Salesman w czasie wielomianowym?
Tak więc problem decyzyjny TSP (problem sprzedawcy podróży) jest NP kompletny . Ale nie rozumiem, w jaki sposób mogę sprawdzić, czy dane rozwiązanie TSP jest w rzeczywistości optymalne w czasie wielomianowym, biorąc pod uwagę, że nie ma sposobu na znalezienie optymalnego rozwiązania w czasie wielomianowym (co jest spowodowane tym, że …
3
Dlaczego relatywizacja jest barierą?
Kiedy wyjaśniłem dowód Baker-Gill-Solovay, że istnieje wyrocznia, którą możemy mieć, , oraz wyrocznia, z którą możemy otrzymać P ≠ N P przyjacielowi, pojawiło się pytanie, dlaczego takie techniki nie nadają się do udowodnienia problemu P ≠ N P i nie mogłem udzielić zadowalającej odpowiedzi.P = N PP=NP\mathsf{P} = \mathsf{NP}P ≠ …
1
Jak trudno policzyć liczbę prostych ścieżek między dwoma węzłami na ukierunkowanym wykresie?
Istnieje prosty algorytm wielomianowy, który decyduje, czy istnieje ścieżka między dwoma węzłami na ukierunkowanym wykresie (po prostu wykonaj rutynowe przemierzanie wykresu za pomocą, powiedzmy, głębokości pierwszego wyszukiwania). Jednak wydaje się, że, co zaskakujące, problem staje się znacznie trudniejszy, jeśli zamiast testowania istnienia chcemy policzyć liczbę ścieżek. Jeśli pozwolimy wierzchołków ścieżki …
1
Problem sumy podzbiorów z wieloma warunkami podzielności
Niech SS.S będzie zbiorem liczb naturalnych. Rozważamy SS.S w częściowej kolejności podzielności, tj. . Pozwolićs1≤s2⟺s1∣s2s1≤s2)⟺s1∣s2)s_1 \leq s_2 \iff s_1 \mid s_2 α(S)=max{|V|∣V⊆S,Vα(S.)=max{|V.|∣V.⊆S.,V.\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, V an antichain .}}\} Jeśli weźmiemy pod uwagę problem sumy podzbioru, w którym wieloseksem liczb jest , to co możemy …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
3
Pomiar trudności wystąpień SAT
Biorąc pod uwagę instancję SAT, chciałbym móc oszacować, jak trudno będzie rozwiązać instancję. Jednym ze sposobów jest uruchamianie istniejących solverów, ale ten rodzaj pokonuje cel oszacowania trudności. Drugi sposób może polegać na szukaniu stosunku klauzul do zmiennych, jak ma to miejsce w przypadku przejść fazowych w losowo-SAT, ale jestem pewien, …
6
Generowanie kombinacji z zestawu par bez powtarzania elementów
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …
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.