Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Minimalne ukończenie wykresu nieparzystych cykli nieparzystych: czy jest trudne NP?
W moich badaniach pojawił się ostatnio następujący interesujący problem: INSTANCJA: Wykres .G ( V, E)G(V,E)G(V, E) ROZWIĄZANIE: Zakończenie akordu nieparzystego cyklu nieparzystego, zdefiniowane jako nadzbiór zestawu krawędzi tak że skompletowany wykres ma właściwość polegającą na tym, że każda krawędź w jest zawarta w bezciężkim cyklu nieparzystym.mi′E′E'miEEsol′( V, E′)G′(V,E′)G'(V, E')sol′G′G' POMIAR: …
2
Rozpoznawanie wykresów liniowych hipergraphów
Wykres liniowy hipergrafu jest (prostym) wykresem G mającym krawędzie H, ponieważ wierzchołki o dwóch krawędziach H sąsiadują w G, jeśli mają niepuste przecięcie. Hypergraph to r- hipergraph, jeśli każda jego krawędź ma co najwyżej r wierzchołków.HHHGGGHHHHHHGGGrrrrrr Jaka jest złożoność następującego problemu: Czy na podstawie wykresu istnieje 3- hipergraph H, taki …
2
Algorytmy aproksymacji super wielomianu dla MAX 3SAT
Stany PCP twierdzenie, że nie ma czasu na wielomian algorytm MAX 3SAT znaleźć spełniającą zadanie klauzule spe wzorze 3SAT chyba P = N P .7 / 8 + ε7/8+ϵ7/8+ \epsilonP.= NP.P=NPP = NP Nie jest to prosta wielomian algorytm czasu, który spełnia klauzul. Tak, możemy to zrobić lepiej niż 7 …
3
Problemy, które są NP-zupełne w przypadku randomizacji lub redukcji P / poli.
W tym pytaniu wydaje się, że zidentyfikowaliśmy naturalny problem, który jest zupełny NP przy redukcjach losowych, ale być może nie przy redukcjach deterministycznych (chociaż zależy to od tego, które niesprawdzone założenia teorii liczb są prawdziwe). Czy znane są inne problemy? Czy istnieją jakieś naturalne problemy, które są NP-zupełne w przypadku …
4
Złożoność komunikacji… Klasy?
Dyskusja : Spędziłem ostatnio trochę czasu na nauce różnych rzeczy w złożoności komunikacji. Na przykład ponownie zapoznałem się z odpowiednim rozdziałem w Arora / Barak, zacząłem czytać kilka artykułów i zamówiłem książkę Kushilevitz / Nisan. Intuicyjnie chcę porównać złożoność komunikacji ze złożonością obliczeniową. W szczególności uderza mnie fakt, że złożoność …
4
Czy nierozstrzygalne atrybuty P stanowią przeszkodę w podejmowaniu decyzji o P w porównaniu z NP? (odpowiedź: może)
Zadaje się pięć powiązanych pytań i oczekuje się jednej zintegrowanej odpowiedzi: P1: Czy istnieją języki które są rozpoznawane wyłącznie przez maszyny Turinga w których wykładników czasu wykonywania nie można rozstrzygnąć ?P.L.LLP.PP Q2: Czy przykłady tych maszyn Turinga mogą być skończone? P3: Czy te maszyny Turinga mogą być konkretnie tworzone? ( …
3
Badanie algorytmów / złożoności algebry liniowej
Szukam dobrej ankiety na temat algorytmów i złożoności algebry liniowej (operacje takie jak rank, inverse, wartości własne, ... dla Boolean, oraz liczby całkowite / racjonalne) z naciskiem na równoległość ( hierarchia ) i algorytmy politime. Nie mogłem znaleźć ostatniego. NCfapFp\mathbb{F}_pN.doNCNC Czy znasz dobrą ostatnią ankietę lub książkę na temat złożoności …
5
Deterministyczny algorytm równoległy do ​​idealnego dopasowania na ogólnych wykresach?
W klasie złożoności istnieją pewne domniemania, że ​​NIE występują w klasie , tj. Problemy z deterministycznymi algorytmami równoległymi. Problem maksymalnego przepływu jest jednym z przykładów. I są problemy, WIĘCEJ, że są w , ale dowód jeszcze nie został znaleziony.N C N C.P.P\mathsf{P}N C.NC\mathsf{NC}N C.NC\mathsf{NC} Znakomite dopasowanie problemem jest to jeden …
2
Czy istnieją opisowe reprezentacje złożoności kwantowych klas złożoności?
Tytuł mniej więcej mówi wszystko, ale myślę, że mógłbym dodać trochę tła i kilka konkretnych przykładów, którymi jestem zainteresowany. Teoretycy złożoności opisowej, tacy jak Immerman i Fagin, scharakteryzowali wiele najbardziej znanych klas złożoności za pomocą logiki. Na przykład NP można scharakteryzować za pomocą zapytań egzystencjalnych drugiego rzędu; P można scharakteryzować …
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.