Pytania otagowane jako decision-problem

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

1
Algorytm sprawdzający, czy język jest prawidłowy
Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest prawidłowy? Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak L={anbn:n∈N}L={anbn:n∈N}L=\{a^n b^n : n \in \mathbb{N}\}), sprawdź, czy język jest prawidłowy, czy nie. Wyobraź sobie, że piszemy serwis internetowy, który pomaga uczniom we wszystkich …
2
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 prosty cykl w o długości większej niż ?kGGGkkk Oczywiście problem dotyczy NP, a …
2
-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 kilku kopaniach znalazłem coś i …
1
Czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych automatów komórkowych?
Próbowałem dowiedzieć się, czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych jednowymiarowych automatów komórkowych. Definicja Niech f(w,i)f(w,i)f(w,i) oznacza konfigurację systemu w kroku czasowym iii . Bardziej formalnie f:A∗×N→A∗f:A∗×N→A∗f:A^*\times \mathbb{N} \to A^* , gdzie AAA jest alfabetem. Definicja. Automat komórkowy zatrzymał się w konfiguracji f(w,i)f(w,i)f(w,i) , jeśli ∀k∈N∀k∈N\forall k\in \mathbb{N} mamy …
3
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, ... , i_{2k}1,2,...,2k1,2,...,2k1, 2, ... , 2k i1+i2≤A1i3+i4≤A2...i2k−1+i2k≤Aki1+i2≤A1i3+i4≤A2...i2k−1+i2k≤Aki_1 + i_2 \leq …
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.