Pytania otagowane jako decision-problem

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

7
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 gra karciana Magic: the Gathering jest zarówno NP, …
2
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 określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
6
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 …
2
Wersja optymalizacyjna problemów decyzyjnych
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Wiadomo, że każdy problem optymalizacji / wyszukiwania ma równoważny problem decyzyjny. Na przykład problem najkrótszej ścieżki Optymalizacja / Wersja: Biorąc pod uwagę nieukierunkowane nieważony wykres a …
5
Dlaczego nie jest to nierozstrzygalny problem w NP?
Najwyraźniej nie ma żadnych nierozstrzygalnych problemów w NP. Jednak według Wikipedii : NP jest zbiorem wszystkich problemów decyzyjnych, dla których przypadki, w których odpowiedź brzmi „tak”, mają […] dowody, które są] weryfikowalne w czasie wielomianowym przez deterministyczną maszynę Turinga. [...] Mówi się, że problem występuje w NP wtedy i tylko …
1
Rozróżnij procedurę decyzyjną w porównaniu do solvera SMT vs provera twierdzeń vs solvera z ograniczeniami
Te terminologie mylą mnie. Jak rozumiem Solver SAT: decyduje o spełnianiu logiki zdań (za pomocą DPLL lub wyszukiwania lokalnego). Procedura decyzyjna to procedura decydująca o spełnieniu pewnej rozstrzygalnej teorii pierwszego rzędu. Solver SMT to solver SAT + procedura decyzyjna. Przysłowie twierdzące wskazuje na coś takiego jak logika dynamiczna, np. Narzędzie …
2
W jaki sposób problem sprzedawcy podróży jest weryfikowalny w czasie wielomianowym?
Rozumiem więc, że problem decyzyjny jest zdefiniowany jako Czy istnieje ścieżka P taka, że ​​koszt jest niższy niż C? i możesz łatwo sprawdzić, czy to prawda, weryfikując otrzymaną ścieżkę. Co jednak, jeśli nie ma ścieżki, która spełniałaby te kryteria? Jak zweryfikowałbyś odpowiedź „nie” bez rozwiązania problemu z najlepszą ścieżką TSP, …
3
Dlaczego nie ma algorytmów aproksymacyjnych dla SAT i innych problemów decyzyjnych?
Mam problem z decyzją o zakończeniu NP. Biorąc pod uwagę przykład problemu, chciałbym zaprojektować algorytm, który wyświetli TAK, jeśli problem jest wykonalny, i NIE, w przeciwnym razie. (Oczywiście, jeśli algorytm nie jest optymalny, popełni błędy.) Nie mogę znaleźć algorytmów aproksymacyjnych dla takich problemów. Szukałem w szczególności SAT i na stronie …
3
Algorytm sprawdzający, czy język jest pozbawiony kontekstu
Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest pozbawiony kontekstu? Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak ), sprawdź, czy język jest pozbawiony kontekstu, czy nie . Wyobraź sobie, że piszemy serwis internetowy, który pomaga uczniom we wszystkich zadaniach domowych; …
2
Czy istnieje skuteczny algorytm równoważności wyrażeń?
np. xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) ? Wyrażenia pochodzą ze zwykłej algebry w szkole średniej, ale ograniczają się do dodawania i mnożenia arytmetycznego (np. 2+2=4;2.3=62+2=4;2.3=62+2=4; 2.3=6 ), bez odwrotności, odejmowania lub dzielenia. Litery są zmiennymi. Jeśli to pomoże, możemy zabronić jakiegokolwiek wyrażenia reprezentowanego przez wartości liczbowe inne niż 111 ; tzn. nie x2x2x^2 ani …
2
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 …
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.