Pytania otagowane jako complexity-theory

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

2
Dlaczego FACTOR w Co-NP?
Mam problem z obejściem problemów PRIME, COMPOSITE, FACTOR i ich powiązania pod względem złożoności. Rozumiem, że PRIME wykazał, że jest w w teście pierwotności AKS i uważam, że działa to również w przypadku KOMPOZYTU.P.PP Jeśli chodzi o CZYNNIK, faA C.T.O R = { ( m , r ) :Such s …
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 …
2
Jak udowodnić P
Zdaję sobie sprawę, że wydaje się to bardzo głupie (lub zbyt oczywiste, by stwierdzić) pytanie. Jednak w pewnym momencie jestem zdezorientowany. Możemy pokazać, że P NP=== wtedy i tylko wtedy, gdy możemy zaprojektować algorytm, który rozwiązuje dowolny przypadek problemu w NP w czasie wielomianowym. Nie rozumiem jednak, jak, u licha, …
1
Czy są jakieś znane problemy z kompletnym AM / czy kompletne AM jest dobrze zdefiniowane?
Jestem ciekawy, czy w klasie złożoności Arthura-Merlina występują jakieś kompletne problemy. Graph Non-Isomorphism (GNI) wydaje się być kanonicznym przykładem problemu w AM, ale prawdopodobnie nie jest kompletny. Chyba zastanawiam się również, czy „kompletny” problem jest dobrze zdefiniowany dla AM. Ponieważ AM = BP.NP, wydaje się, że przejście na „redukcję” do …
2
Czy uogólniony XOR-SAT jest sprawnie rozwiązywalny?
Widziałem, w jaki sposób XOR-3-SAT można skutecznie rozwiązać (na przykład zobacz sekcję „Zgodność XOR” we wpisie w Wikipedii na temat problemu logicznej satysfakcji ). Zastanawiam się nad podstawowym pytaniem: czy XOR-k-SAT można skutecznie rozwiązać w przypadku formuł o różnej ilości literałów w klauzuli? Naprawdę chciałbym wiedzieć, czy możemy zwiększyć liczbę …
2
Grupowanie izomorfizmu do izomorfizmu grafowego
Czytając niektóre blogi o złożoności obliczeniowej (na przykład tutaj ) przyswoiłem sobie pogląd, że podjęcie decyzji, czy dwie grupy są izomorficzne jest łatwiejsze niż przetestowanie dwóch wykresów pod kątem izomorfizmu. Na przykład na podanej stronie napisano, że izomorfizm grafów jest bardziej ogólnym problemem niż izomorfizm grupowy. Dlatego stawiam następujące Biorąc …
2
Czy kompletność coNP implikuje twardość NP?
Czy kompletność coNP implikuje twardość NP? W szczególności mam problem, który wykazałem, że jest kompletny coNP. Czy mogę twierdzić, że jest to trudne NP? Zdaję sobie sprawę, że mogę żądać twardości coNP, ale nie jestem pewien, czy ta terminologia jest standardowa. Nie mam nic przeciwko twierdzeniu, że jeśli problem NP-zupełny …
2
Wykazać kompletność NP decydującej o satysfakcji monotonicznej formuły boolowskiej
Próbuję rozwiązać ten problem i naprawdę walczę. Monotoniczne logiczna wzór jest wzorem w zdań logiki, gdy wszystkie literałami dodatnie. Na przykład, ( x1∨ x2)) ∧ ( x1∨ x3)) ∧ ( x3)∨ x4∨ x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5) jest monotoniczną funkcją logiczną. …
4
Czy złożoność problemów silnie NP-trudnych lub -kompletnych zmienia się, gdy ich dane wejściowe są kodowane w sposób jednoznaczny?
Czy trudność silnie trudnego NP lub problemu NP-zupełnego (jak np. Zdefiniowano tutaj ) zmienia się, gdy jego wejście jest jednoargumentowe zamiast kodowane binarnie? Jaką różnicę ma to, że wejście problemu silnie trudnego NP jest zakodowane w sposób jednoznaczny? Chodzi mi o to, że jeśli wezmę na przykład słabo NP-kompletny problem …
5
Wada mojego NP = dowód CoNP?
Mam ten bardzo prosty „dowód” na NP = CoNP i myślę, że gdzieś coś zrobiłem źle, ale nie mogę znaleźć, co jest nie tak. Czy ktoś może mi pomóc? Niech A będzie pewnym problemem w NP, i niech M będzie decydującym dla A. Niech B będzie dopełnieniem, tj. B jest …
3
Dlaczego większe rozmiary wejściowe oznaczają trudniejsze instancje?
Poniżej załóżmy, że pracujemy z maszyną Turinga z nieskończoną taśmą. Wyjaśniając komuś pojęcie złożoności czasowej i dlaczego mierzy się ją względem wielkości wejściowej instancji, natknąłem się na następujące twierdzenie: [..] Na przykład naturalne jest, że potrzeba więcej kroków, aby pomnożyć dwie liczby całkowite przez 100 000 bitów, niż, powiedzmy, pomnożenie …
3
Jak szybko możemy znaleźć wszystkie kombinacje czterech kwadratów, które sumują się do N?
Pytanie zostało zadane w Stack Overflow ( tutaj ): Biorąc pod uwagę całkowitą wydrukować wszystkie możliwe kombinacje wartości całkowitych z i dzięki którym rozwiązuje się równanie .N.N.NA , B , C.ZA,b,doA,B,CrereDZA2)+ B2)+ C.2)+ D2)= NZA2)+b2)+do2)+re2)=N.A^2+B^2+C^2+D^2 = N To pytanie jest oczywiście związane z hipotezą Bacheta w teorii liczb (czasami nazywaną …
2
Wyrocznia do oddzielenia NP od CoNP
Jak udowodnić, że ? Właśnie szukam takiej wyroczni TM M i języka rekurencyjnego L ( M ) = L, dla którego to się utrzymuje.NPA≠coNPANPA≠coNPA\mathsf{NP}^A \neq \mathsf{coNP}^AMMML(M)=LL(M)=LL(M) = L Znam dowód gdzie można pokazać, że nie jest wyrocznią takie, że P ≠ N P i wyrocznią takie, że P = N …
1
Co to jest klasa złożoności
Co oznacza klasa złożoności ? Wiem, że jest klasą złożoności, która zawiera języki dla których istnieje wielomianowa niedeterministyczna maszyna Turinga taka, że iff liczba akceptujących stanów maszyny na wejściu jest nieparzysta. ⊕ P A M x ∈ A M x⊕P⊕P⊕P⊕P\oplus P^{\oplus P}⊕P⊕P\oplus PAAAMMMx∈Ax∈Ax \in AMMMxxx Ale co oznacza ? Po …
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.