Instancja: Niekierowany wykres GsolG z dwoma wyróżniającymi się wierzchołkami i liczbą całkowitą .s≠ts≠ts\neq tk≥2k≥2)k\geq 2 Pytanie: Czy istnieje ścieżka w , taka, że ścieżka dotyka co najwyżej wierzchołków? (Ścieżka dotyka wierzchołka, jeśli wierzchołek znajduje się na ścieżce lub ma ścieżkę...
Właściwość wykresu jest nazywana dziedziczną, jeśli zostanie zamknięta w odniesieniu do usuwania wierzchołków (tj. Wszystkie indukowane podgrupy dziedziczą właściwość). Właściwość graf nazywa się addytywną, jeśli jest zamknięta w odniesieniu do przyjmowania rozłącznych związków. Nie jest trudno...
Jednym z głównych problemów w TCS jest problem wyrażania stałego jako wyznacznika. Czytałem artykuł Agrawala Determinant vs. Permanent i w jednym akapicie twierdzi, że odwrotny problem jest łatwy. Łatwo jest zauważyć, że wyznacznikiem macierzy można wyrazić jako stałe powiązanego macierzy X ,...
Czy N P.N P.∩c o N P= N P.N.P.N.P.∩dooN.P.=N.P.\mathsf{NP^{NP \,\cap\, coNP}=NP}trzymać? Najwyraźniej N P.N P.≠ N P.N.P.N.P.≠N.P.\mathsf{NP^{NP}\neq NP} , ale wydaje mi się, że N P ∩ c o N PN.P.∩dooN.P.\mathsf{NP\cap coNP} jest „deterministyczna”, co pozwala mi wierzyć, że to prawda. Czy istnieje...
Szybkie wyszukiwanie w Internecie doprowadziło mnie do przekonania, że „APXHardness implikuje, że nie ma QPTAS dla problemu, chyba że [jakaś klasa złożoności] jest zawarta w [innej klasie złożoności]” i jest również dobrze znana! Wygląda na to, że wszyscy o tym wiedzą oprócz mnie. Niestety nie...
Czy możemy udowodnić, że dla każdego języka który nie jest -hard (zakłada to ), ? Alternatywnie, czy można to udowodnić przy jakichkolwiek uzasadnionych założeniach?L∈NPL∈NPL\in\mathsf{NP}NPNP\mathsf{NP}P≠NPP≠NP\mathsf P \ne \mathsf{NP}PL≠PSATPL≠PSAT\mathsf{P}^L \ne...
Strona wikipedii na PSPACE wspomina, że włączenie nie jest znane jako ścisłe (niestety bez odnośników).NL⊂PHNL⊂PHNL\subset PH P1: Co z i - czy są one znane jako ścisłe?L⊂PHL⊂PHL\subset PHL⊂P#PL⊂P#PL\subset P^{\#P} P2: Jeśli nie, czy istnieje ustalona klasa która zawiera i dla której nie...
Mam część próbnej próby ⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}. Próba dowodowa polega na zmniejszeniu karpu z⊕P⊕P\oplus \mathbf{P}-kompletny problem ⊕⊕\oplus3-REGULARNA POKRYWA VERTEX do SAT. Biorąc pod uwagę sześcienny wykres GGG, redukcja generuje wzór CNF FFF posiadający obie...
Wejściowego, to świat i rodzina podzbiorów , powiedzmy, . Zakładamy, że w podzbiory może obejmować , czyli .UUUUUUF⊆2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Przyrostowe sekwencja Pokrycie jest ciągiem podzbiorów w , powiedzmy, , który spełniafaF{\cal F}ZA=...
Niech będzie funkcją logiczną o czułości s ( f ) i czułości bloku b s ( f ) .fafafs ( f)s(fa)s(f)b s ( f)bs(fa)bs(f) Hipoteza domniemania czułości według bloku czułości stwierdza, że istnieje takie, że ∀ f , b s ( f ) ≤ s ( f ) c .c > 0do>0c>0∀ f, b s ( f ) ≤ s (...
Naturalna bariera dowodowa Razborova i Rudicha mówi, że przy wiarygodnych założeniach kryptograficznych nie można mieć nadziei na oddzielenie NP od P / poli poprzez znalezienie kombinatorycznych właściwości funkcji, które są konstruktywne, duże i użyteczne. Istnieje kilka dobrze znanych wyników,...
Szukam listy o znanej lub nieznanej złożoności różnych problemów teoretycznych / algebraicznych. Na przykład, GCD w jest otwarty,N.do1NC1NC^1 faktoring w jest otwarty,P.PP obliczanie kohomologii snopów to -hard# P#P\#P , Arora i Barak stwierdzają, że wariant faktoringu jest -Complete (choć nie...
Jakie są niektóre (mało znane) twierdzenia, że jeśli prawda, PH musi się załamać? Docenia się odpowiedzi zawierające krótkie stwierdzenie wysokiego poziomu z referencjami. Próbowałem przeszukać wstecz bez większego
oznacza N P ⊆ P / P O l y , który z kolei ma wpływ interesujące jak załamania wielomianu hierarchii.P/poly=NP/polyP/poly=NP/polyP/poly = NP/polyNP⊆P/polyNP⊆P/polyNP \subseteq P/poly Czy są interesujące implikacje dla ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq
w 1979 r. Hopcroft / Ullman napisał, że L ⊆ P ⊆ NP ⊆ PSpace jest znany, ale L ⊊ PSpace jest jedynym właściwym (i trywialnym) zabezpieczeniem znanym, chociaż wszystkie są przypuszczane, że są odpowiednimi zabezpieczeniami i „tam, gdzie rzeczy nadal istnieją” ~ 4 dekady później . od tego czasu...
Redukcja karp jest wielomianową obliczalną w czasie wielokrotnością redukcji między dwoma problemami obliczeniowymi. Wiele redukcji Karp jest w rzeczywistości funkcjami jeden-jeden. Rodzi to pytanie, czy każda redukcja Karp jest iniekcyjna (funkcja jeden do jednego). Czy istnieje naturalny...
Zastanawiam się, co by się stało, gdyby w definicji (wielomianowa hierarchia, patrz np. Tutaj ) rola zostałaby zastąpiona przez ?PHPHPHNPNPNPRPRPRP Wydaje się, że można jeszcze zbudować hierarchię, tak samo jak jest zbudowany, tylko za pomocą wszędzie zamiast i zamiast . Nazwijmy to Randomized...
Niech oznacza minimalny rozmiar (niemonotonowego) arytmetycznego obwodu obliczającego dany wielomianowy wielomian i oznaczają minimalny rozmiar ( obwodu logicznego obliczającego wersję logiczną z zdefiniowane
Rozważam język wszystkich zadowalających formuł logicznych zdań, SAT (aby upewnić się, że ma to skończony alfabet, będziemy kodować litery zdań w odpowiedni sposób [edytuj: odpowiedzi wskazały, że odpowiedź na pytanie może nie być solidna pod różne kodowania, więc trzeba być bardziej szczegółowym -...
Łatwe spostrzeżenie, że, jeżeli problem jest rozstrzygalne przez wielomian czasu niedeterministycznych programu przy O ( log n ) niedeterministycznych bitów (czyli wszystkie świadków logarytmiczna długości), a następnie ∈ P .ZAAAO(logn)O(logn)O(\log n)A∈PA∈PA \in \mathsf{P} Jeśli ktoś zadaje...