Pytania oznaczone «decision-problem»

Pytanie w jakimś formalnym systemie z odpowiedzią tak lub nie.

64
Czy ustawodawstwo NP jest kompletne?

Chciałbym wiedzieć, czy były prace związane z kodeksem prawnym złożoności. W szczególności, przypuśćmy, że mamy problem decyzyjny „Czy biorąc pod uwagę tę książkę prawniczą i ten szczególny zestaw okoliczności, pozwany jest winny?” Do jakiej klasy złożoności należy? Są wyniki, które dowiodły, że...

28
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 nie była...

28
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...

12
Czy problem korespondencyjny występuje w NP?

Właśnie przeczytałem kilka stron w książce Sipsera Wprowadzenie do teorii obliczeń na temat problemu z korespondencją pocztową i myślę, że PCP jest w rzeczywistości w NP. Certyfikującej wynosi: dla konfiguracji wejściowej stos łączenie T 1 , T 2 , . . . , t n jako ciąg t i konkatenacja b 1 , b(...

11
Najdłuższy cykl zawarty w dwóch cyklach

Czy następujący problem NP-jest kompletny? (Zakładam, że tak). Wprowadź: niekierowany wykres, na którym zbiór zboczy może zostać rozłożony na dwa proste cykle rozłączne od krawędzi ( nie są one częścią danych wejściowych).k∈N,G=(V,E)k∈N,G=(V,E)k \in \mathbb{N},G=(V,E) Pytanie: Czy istnieje...

11
-algebrze na wejściu algorytmu

Chcę sprecyzować, co to znaczy podać algebrę jako dane wejściowe do algorytmu i nie znalazłem zbyt wiele literatury na ten temat. Najpierw chciałbym zapytać, czy możesz polecić książkę lub artykuł, który porusza temat analizy złożoności algebr nad polami i jasno określa problem decyzyjny . Po...

10
Przypisanie numeru

Biorąc pod uwagę liczb tak, że istnieje przypisanie liczb który jest permutacją taki, żeA 1 ≤ A 2 ≤ . . . ≤ A k k ∑kkkA1≤A2≤...≤AkA1≤A2≤...≤AkA_1 \leq A_2 \leq ... \leq A_k∑i=1kAi=k(2k+1)∑i=1kAi=k(2k+1)\sum\limits_{i=1}^k A_i = k(2k + 1)i1,i2,...,i2ki1,i2,...,i2ki_1, i_2, ... ,...