Pytania otagowane jako complexity-theory

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

3
P, NP i specjalistyczne maszyny Turinga
Jestem w pewnym sensie nowy, ale bardzo zainteresowany dziedziną obliczeń i teorii złożoności, i chcę wyjaśnić moje rozumienie, w jaki sposób klasyfikować problemy i jak silnie problemy odnoszą się do maszyny używanej do ich rozwiązywania. Moje zrozumienie Standardowa maszyna Turinga - maszyna Turinga, która ma skończony alfabet, skończoną liczbę stanów …
2
Czy funkcje wyższego rzędu zapewniają większą moc programowaniu funkcjonalnemu?
Zadałem podobne pytanie na cstheory.SE . Zgodnie z tą odpowiedzią na Stackoverflow istnieje algorytm, który w nieliniowym czystym funkcjonalnym języku programowania ma złożoność , podczas gdy tym samym algorytmem w programowaniu imperatywnym jest Ω ( n ) . Dodanie lenistwa do języka FP spowodowałoby, że algorytm Ω ( n ) …
1
Ograniczona wersja problemu Clique?
Rozważ następującą wersję problemu Kliki, w której dane wejściowe mają rozmiar a my poprosimy o znalezienie kliki o rozmiarze . Ograniczeniem jest to, że procedura decyzyjna nie może zmienić wykresu wejściowego na żadną inną reprezentację i nie może użyć żadnej innej reprezentacji do obliczenia swojej odpowiedzi, oprócz dodatkowych bitów poza …
2
Udowodnienie, że DOUBLE-SAT jest NP-zakończone
Dobrze znany problem SAT został tu zdefiniowany dla odniesienia. Problem DOUBLE-SAT jest zdefiniowany jako DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least two satisfying assignments}\} Jak udowodnimy, że jest kompletny NP? Doceniony zostanie więcej niż jeden …
3
Czy istnieje abstrakcyjna maszyna, która może rejestrować zużycie energii?
Zgłaszając złożoność algorytmu algorytmu, zakłada się, że obliczenia leżące u jego podstaw są wykonywane na jakiejś abstrakcyjnej maszynie (np. RAM), która przybliża nowoczesny procesor. Takie modele pozwalają nam raportować złożoność algorytmów w czasie i przestrzeni. Teraz, przy rozproszeniu GPGPU , zastanawia się, czy istnieją dobrze znane modele, w których można …
2
MIN-2-XOR-SAT i MAX-2-XOR-SAT: czy są NP-twarde?
Jaka jest złożoność MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} i MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Czy są w P? Czy są twarde NP? Aby sformalizować to dokładniej, pozwól Φ(x)=∧niCi,Φ(x)=∧jandoja,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, gdzie x=(x1,…,xm)x=(x1,…,xm)\mathbf{x} = (x_1,\dots,x_m) a każda klauzula CiCiC_i ma postać (xi⊕xj)(xi⊕xj)(x_i \oplus x_j) lub (xi⊕¬xj)(xi⊕¬xj)(x_i \oplus \neg x_j) . Problem 2-XOR-SAT2-XOR-SAT\text{2-XOR-SAT} polega na znalezieniu przypisania do xx\mathbf{x} które …
2
Czy można rozwiązać dowolny problem NP-Complete przy użyciu co najwyżej przestrzeni wielomianowej (ale przy użyciu czasu wykładniczego?)
Czytam o NPC i jego związku z PSPACE i chcę wiedzieć, czy problemy NPC można rozwiązać w sposób deterministyczny za pomocą algorytmu o najgorszym przypadku wymaganej przestrzeni wielomianowej, ale potencjalnie zajmującego wykładniczy czas (2 ^ P (n), gdzie P jest wielomianem). Co więcej, czy można ją ogólnie uogólnić na EXPTIME …
2
Problemy, które wydają się wykładnicze, ale są P
Próbuję zbudować listę algorytmów / problemów, które są „wyjątkowo przydatne”, jak w przypadku rozwiązywania problemów, które „wydają się” z natury bardzo wykładnicze, ale mają jakiś szczególnie sprytny algorytm, który ostatecznie je rozwiązuje. Przykłady tego, co mam na myśli: Programowanie liniowe (algorytm simpleksowy jest czasem wykładniczym; znalezienie rozwiązania wielomianowego czasu zajęło …
1
Czy pakowanie torby prezentów jest łatwiejsze dla Ruperta niż Świętego Mikołaja?
Lub: Czy potrzebujemy Ruperta, aby w ogóle otrzymać prezenty? Pomijając problemy z routingiem, Święty Mikołaj napotyka następujący problem (wiele, wiele razy): Biorąc pod uwagę torbę o pojemności¹ i zestaw prezentów , każdy o rozmiarze , chce uszczęśliwić dzieci . Ze wszystkich list życzeń wie, że potomne wartości prezentują dokładnie bardzo …
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.