Pytania otagowane jako complexity-theory

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

1
Dlaczego ta funkcja jest obliczalna w czasie ?
My podręcznik mówi „określamy funkcji następująco: i . Zauważ, że biorąc pod uwagę , możemy łatwo znaleźć w czasie liczbę taką, że jest umieszczone pomiędzy i . "f:N→Nf:N→Nf\colon \mathbb{N}\to\mathbb{N}f(1)=2f(1)=2f(1)=2f(i+1)=2f(i)1.2f(i+1)=2f(i)1.2f(i+1)=2^{f(i)^{1.2}}nnnO(n1.5)O(n1.5)O(n^{1.5})iiinnnf(i)f(i)f(i)f(i+1)f(i+1)f(i+1) Jak mogę się przekonać, że tak naprawdę możemy łatwo znaleźć w czasie ? Ponieważ jest zdefiniowane rekurencyjnie, myślę, że musimy obliczyć …
2
Jaka jest złożoność obliczania współczynnika korelacji rang Spearmana?
Byłem studiowania Współczynnik korelacji rang Spearmana ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2−−−−−−−−−−−−−−−−−−−√ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}} . dla dwóch list i . Jaka jest złożoność algorytmu?x1,…,xnx1,…,xnx_1, \dots, x_ny1,…,yny1,…,yny_1, \dots, y_n Skoro algorytm powinien po prostu obliczać odejmowań, to czy można być ?nnnO(n)O(n)O(n)
2
Robi
Czy z dostępem Oracle do większy niż ? Rozumiem, że to tylko maszyna Turinga, która może wysyłać zapytania do innej maszyny , jeśli tak, to może symulować ? Czy coś jest nie tak z tym argumentem?NPNPNPNPNPNPNPNPNPNPNPNPNPNP^ {NP}NPNPNPNPNPNPNPNPNPNPNP^{NP}
6
Czy istnieją odmiany regularnych środowisk uruchomieniowych notacji Big-O-Notation?
Istnieje wiele Notacji, takich jak lub i tak dalej. Zastanawiałem się, czy w rzeczywistości istnieją odmiany takich jak lub , czy też są matematycznie niepoprawne.OOOO(n)O(n)O(n)O(n2)O(n2)O(n^2)O(2n2)O(2n2)O(2n^2)O(logn2)O(log⁡n2)O(\log n^2) A może słuszne byłoby stwierdzenie, że można poprawić do ? Nie mogę i nie muszę jeszcze wymyślać środowisk uruchomieniowych i nie muszę niczego poprawiać, …
2
Czy istnieją problemy „pełne (O)”?
Wiele klas złożoności ma „kompletne” problemy. Czy istnieją kompletne problemy dla klasy złożoności problemów, które można rozwiązaćO ( 1 )O(1)O(1) czas? Komplikacja polega na tym, że klasa ta zależy od modelu obliczeniowego; problem można rozwiązaćO ( 1 )O(1)O(1)czas w jednym rozsądnym modelu obliczeniowym, ale nie w innym, biorąc pod uwagę, …
1
Sztuczka zastosowana w dowodzie podwójnie wykładniczej złożoności arytmetyki Presburger'a
Wysłałem to na MathUnderflow, ale nie otrzymałem odpowiedzi, więc pomyślałem, że spróbuję tutaj, Czytam stary artykuł Rabina i Fischera [opublikuje link, jeśli to możliwe], gdzie między innymi udowodniono podwójnie wykładniczą złożoność arytmetyki Presburger'a. Dowód opiera się na istnieniu formuły jan( x )In(x)I_{n}(x) nieformalne stwierdzenie „x &lt;2)2)k x + 1x&lt;22kx+1x < …
2
Znaleźć centralny punkt w zestawie punktów metrycznych przestrzeni, w mniej niż ?
Mam zestaw punktów, które są zdefiniowane w przestrzeni metrycznej - więc mogę zmierzyć „odległość” między punktami, ale nic więcej. Chcę znaleźć najbardziej centralny punkt w tym zestawie, który definiuję jako punkt o minimalnej sumie odległości do wszystkich innych punktów. Obliczenia metryczne są powolne, więc w miarę możliwości należy go unikać.nnn …
2
Czy możliwe jest sortowanie liczb całkowitych w O (n) w modelu transdychotomicznym?
Według mojej wiedzy nie istnieje algorytm najgorszego przypadku, który rozwiązuje następujący problem:O ( n )O(n)O(n) Biorąc pod uwagę ciąg długości składający się ze skończonych liczb całkowitych, znajdź permutację, w której każdy element jest mniejszy lub równy jego następcy.nnn Ale czy istnieje dowód, że nie istnieje, w transdychotomicznym modelu obliczeniowym ? …
4
Czy unikalność elementu można rozwiązać w deterministycznym czasie liniowym?
Rozważ następujący problem: Dane wejściowe : wyświetla liczb całkowitychX,YX,YX,Y Cel : ustalenie, czy istnieje liczba całkowita xxx która znajduje się na obu listach. Załóżmy, że obie listy X,YX,YX,Y mają rozmiar nnn . Czy dla tego problemu istnieje deterministyczny algorytm czasu liniowego? Innymi słowy, czy możesz rozwiązać ten problem deterministycznie w …
2
W jaki sposób korzystanie z maszyn wyroczni Turinga nie prowadzi do sprzeczności?
W jaki sposób możemy zagwarantować, że podczas korzystania z maszyn Turinga Oracle nadal będziemy wydawać prawidłowe i prawidłowe oświadczenia o klasach złożoności? Według mojego zrozumienia (na podstawie definicji podanych we wprowadzających podręcznikach na ten temat) maszyny oracle Turing mogą określić status członkostwa w łańcuchu znaków w odniesieniu do języka Oracle …
1
Rozkłady prawdopodobieństwa i złożoność obliczeniowa
To pytanie dotyczy przecięcia teorii prawdopodobieństwa i złożoności obliczeniowej. Jednym kluczowym spostrzeżeniem jest to, że niektóre rozkłady są łatwiejsze do wygenerowania niż inne. Na przykład problem Biorąc pod uwagę liczbę nnn, zwróć równomiernie rozłożoną liczbę jaii z 0 ≤ i &lt; n0≤i&lt;n0 \leq i < n. jest łatwy do rozwiązania. …
1
Jakie są odpowiednie izomorfizmy między językami formalnymi?
Język formalny nad alfabetem jest podzbiorem , czyli zbiór słów nad tym alfabecie. Dwa formalne języki i są sobie równe, jeśli odpowiadające im zbiory są ponadto równe jako podzbiory . W teorii złożoności można używać języków, aby sformalizować pojęcie „problemu”. Można narzekać, że „ogólnie” ekstensywna równość jest nierozstrzygalna, ale wierzę, …
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.