Pytania otagowane jako cc.complexity-theory

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

1
Czy wymaganie jednoznaczności poprawnych odpowiedzi dla Merlina ogranicza moc protokołów Arthur-Merlin?
Preambuła. Klasa złożoności AM to te problemy, które można rozwiązać za pomocą dwóch okrągłych interaktywnych systemów dowodowych między sprawdzonym „Merlinem” a weryfikatorem „Arthurem”. Problem - który testuje niektóre właściwości obiektu X - występuje w AM, jeśli: W przypadku TAK , dla losowego komunikatu „wyzwanie” (o wielomianowej długości) Arthur generuje z …
1
Ranking trudności trudnych problemów NP w praktyce
To pytanie jest ściśle związane z innym postem: Przejścia fazowe w trudnych problemach NP, ale jest nieco inne. Chociaż pytanie dotyczy twardości poszczególnych przypadków trudnych problemów NP, chodzi o uszeregowanie trudności tych samych przypadków. Istnieje wiele bibliografii na temat efektu znanego jako Przejście Fazowe . W szczególności w przypadku losowych …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
3
Teorie charakteryzujące klasy złożoności obliczeniowej
Czytając artykuł „ Teoria aplikacyjna dla FPH ”, można natknąć się na następujący fragment: Biorąc pod uwagę teorie charakteryzujące klasy złożoności obliczeniowej, istnieją trzy różne podejścia: w jednym funkcje, które można zdefiniować w teorii, są „automatycznie” w ramach pewnej klasy złożoności. Na takim koncie należy ograniczyć składnię, aby zagwarantować, że …
1
Projektowanie i złożoność algorytmów - jak myśleć w ten „sposób”?
Moje pytanie jest ogólne: jak zacząć myśleć o projektowaniu i złożoności algorytmów? Mam zamiar podjąć kurs magisterski z projektowania algorytmów. Zapisałem się na to wcześniej, ale porzuciłem go później, ponieważ nie mogłem nadążyć. Muszę wziąć ten kurs jako wymóg. Czy istnieje „sztuczka” do myślenia w ten sposób? Wiem, że jest …
3
Złożoność kolorowania krawędzi na wykresach płaskich
3 krawędzi barwienia wykresów sześcienny -Complete. Twierdzenie o czterech kolorach jest równoważne z tym, że „Każdy sześcienny płaski wykres bez mostka ma 3 krawędzie do pokolorowania”.N.P.N.P.NP Jaka jest złożoność 3-krawędziowego kolorowania sześciennych wykresów płaskich? Ponadto, przypuszcza się, że -edge barwiący N P -hard dla płaskich wykresów z maksymalnym stopniu hemibursztynianu …
4
Czy istnieją znane funkcje z następującą właściwością sumy bezpośredniej?
To pytanie można zadać albo w ramach złożoności obwodów obwodów boolowskich, albo w ramach teorii złożoności algebraicznej, lub prawdopodobnie w wielu innych ustawieniach. Łatwo jest wykazać, licząc argumenty, że istnieją funkcje logiczne na wejściach N, które wymagają wykładniczo wielu bramek (choć oczywiście nie mamy żadnych wyraźnych przykładów). Załóżmy, że chciałbym …
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.