W przypadku wielomianowego problemu wyszukiwania lokalnego wiemy, że musi istnieć co najmniej jedno rozwiązanie (lokalne optimum). Jednak może istnieć wiele innych rozwiązań, jak trudno jest policzyć liczbę rozwiązań problemu z kompletnym PLS? Jestem szczególnie zainteresowany w problemu...
Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji...
Załóżmy, że otrzymujemy tablicę A[1..n]A[1..n]A[1..n] zawierającą nieujemne liczby całkowite (niekoniecznie różne). BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. Oczywistym rozwiązaniem jest sortowanie a następnie obliczanie . Daje to algorytm działający w czasie w...
Klasa UP jest zdefiniowana jako taka: Klasa problemów decyzyjnych rozwiązanych przez maszynę NP, taką jak Jeśli odpowiedź brzmi „tak”, akceptuje dokładnie jedną ścieżkę obliczeniową. Jeśli odpowiedź brzmi „nie”, wszystkie ścieżki obliczeniowe odrzucają. Próbuję rozwinąć intuicję dla tej...
Problem „drugiego ” to problem decydowania o istnieniu innego rozwiązania innego niż niektóre dane rozwiązanie problemu.XXX W przypadku niektórych uzupełnieniem druga wersja rozwiązania to zupełne (decydujące o istnieniu innego rozwiązania dla częściowego problemu częściowego uzupełnienia kwadratu...
Impagliazzo, Paturi i Calabro, Impagliazzo, Paturi wprowadzili hipotezę czasu wykładniczego (ETH) i hipotezę silnie wykładniczego czasu (SETH). Z grubsza, SETH mówi, że nie ma algorytmu, który rozwiązuje SAT w czasie . 1,99n1,99n1.99^n Zastanawiałem się, co to znaczy złamać SETH. Zdecydowanie...
Szukam klasy złożoności, który dotyczy APX jako BPP dotyczy P. Już samo pytanie tutaj , ale być może będzie TCS być bardziej owocne lokalizacja odpowiedzi. Powodem tego pytania jest to, że w praktycznych problemach często trzeba znaleźć przybliżone odpowiedzi (a więc APX) z wystarczająco wysoką...
Po przeczytaniu powiązanego pytania dotyczącego niekonstruktywnych dowodów istnienia algorytmów, zastanawiałem się, czy istnieją metody pokazania istnienia „małych” (powiedzmy, stanowych) maszyn obliczeniowych bez ich budowania. Formalnie: załóżmy, że otrzymaliśmy język i naprawiliśmy jakiś...
Skrzyżowane z MO . Niech CCC będzie klasą grafu zdefiniowaną przez skończoną liczbę zabronionych indukowanych podrożników, z których wszystkie są cykliczne (zawierają co najmniej jeden cykl). Czy istnieją problemy związane z grafem trudnym dla NP, które można rozwiązać w czasie wielomianowym...
To mnie dezorientuje. Jednym z łatwych przypadków liczenia jest sytuacja, gdy problem decyzyjny występuje w i nie ma rozwiązań.PPP Wykład pokazuje, że problem zliczania liczby idealnych dopasowań na grafie dwustronnym (równoważnie, zliczanie liczby okładek cykli na ukierunkowanym wykresie) jest...
Rozważ następujący problem: Biorąc pod uwagę dwa ciągi x, y, zdecyduj, czy istnieje homomorfizm ciągu f taki, że f (x) = y. Łatwo jest pokazać, że problem ten jest w . Czy są inne rzeczy, które możemy powiedzieć o tym problemie? Jest to na przykład w c o N P lub nawet P...
Jak wiemy, definicja złożoności obliczeniowej algorytmu prawie nie budzi kontrowersji, ale definicja złożoności obliczeniowej rzeczywistych lub modeli obliczeniowych rzeczywistych nie jest w takim przypadku. Model i model Bluma i Smalesa znamy w książce Computable Analysis. I pozornie model w...
Niech będzie polem. Jak zwykle dla f ∈ k [ x 1 , x 2 , … , x n ] definiujemy L ( f ) jako złożoność linii f względem k w linii prostej . Niech K będzie zbiorem jednomianów f , a mianowicie jednomianów, które występują w f z niezerowym współczynniku.kkkf∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in...
Załóżmy, że nasze dane wejściowe są binarne i musimy wyprowadzić ⌊ x / c ⌋ , gdzie c jest jakąś stałą liczbą całkowitą. To tylko zmiana, jeśli c jest potęgą dwóch, ale co z innymi liczbami? Czy możemy to zrobić z obwodem o stałej głębokości dla każdego c ? Co z c = 3 ?xxx⌊x/c⌋⌊x/c⌋\lfloor x/c...
Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno...
Czy skończony odwrotny problem izomorfizmu półgrupy GI jest kompletny ? Tutaj zakłada się, że skończone odwrotne półgrupy są podane przez ich tabliczki
Drzewo decyzyjne do odczytu definiuje się następująco: and F danej ł s e się do odczytu po drzew decyzyjnych.T.R u eTrueTruefaa l s eFalseFalse Jeśli i B są drzewami decyzyjnymi do odczytu, a x jest zmienną nie występującą w A i B , to ( x ∧ A ) ∨ ( ˉ x ∧ B ) jest również drzewem decyzyjnym do...
Zastanawiałem się, do której klasy należy ten język: jest wykresem, jest liczbą naturalną, a jest liczbą chromatycznąL = { ⟨ G , K ⟩ | GL.={⟨sol,k⟩∣solL =\{ \langle G,k \rangle \mid G kkkkkkG }sol}G\} Myślałem o jako (1) „nie ma zabarwienia kolorów k-1” i (2) „jest zabarwienie kolorów ”. Teraz...
Istnieją teorie grafów algorytmicznych / teoria liczb / kombinatoryka / teoria informacji / teoria gier. Czy istnieje algorytmiczna analiza matematyczna? Według wiki analiza matematyczna obejmuje teorie różniczkowania, całkowania, miary, limitów, szeregów nieskończonych i funkcji...
Krótko mówiąc, pytanie brzmi: w jakim stopniu zdolność obliczeniowa do trudnych zadań naprawdę pomaga w rozwiązywaniu łatwych zadań. (Mogą istnieć różne sposoby uczynienia tego pytania interesującym i nietrywialnym, a oto jedna z takich prób). Pytanie 1: Rozważ obwód rozwiązywania SAT dla formuły...