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 ,...
Lemat Johnsona-Lindenstraussa pozwala reprezentować punkty w przestrzeni o dużych wymiarach w punktach o niższych wymiarach. Podczas znajdowania najlepiej dopasowanych mniejszych wymiarów, standardową techniką jest znalezienie rozkładu wartości w liczbie pojedynczej, a następnie wzięcie...
Języki Dyck definiuje następująca gramatyka S → S S.Dyck(k)Dyck(k)\mathsf{Dyck}(k) nad zbiorem symboli { ( 1 , … , ( k , ) 1 , … , ) k } . Języki intuicyjnie Dyck są językami zbilansowanych nawiasów k innego rodzaju. Na przykład (S→SS|(1S)1|…|(kS)k|ϵS→SS|(1S)1|…|(kS)k|ϵ S \rightarrow SS \,|\, (_1...
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...
Płaska wykres przedstawia wykres, który może być osadzony w płaszczyźnie, bez konieczności przekraczania krawędzie. Niech będzie - jednolitym hipergraphem, tj. Hipergraphem takim, że wszystkie jego hipergezy mają rozmiar k.kG = ( X, E)G=(X,E)G=(X,E)kkk Wykonano już pewne prace związane z...
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...
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny? Problem pustki dla modelu obliczeniowego (np. Automat skończony, automat przemienny, automat kwantowy z ograniczeniem błędu z licznikiem, deterministyczny LBA itp.) Polega na ustaleniu, czy dla danej takiej...
Dobrze wiadomo, że permutacje sortujące według transpozycji są w , ponieważ minimalna liczba transpozycji wymagana do sortowania π ∈ S n wynosi dokładnie i n v ( π ) = { ( i , j ) ∈ [ n ] × [ n ] : i < j i π ( i ) > π ( j ) }PP\sf{P}π∈Snπ∈Sn\pi \in
Czy to możliwe, że ? Czy są interesujące konsekwencje takiego ograniczenia? Czy byłoby to sprzeczne z hipotezą o wykładniczym czasie?S.A T.¯¯¯¯¯¯¯¯¯¯∈ N.T.jaM.mi( exp( n0,9) )S.ZAT.¯∈N.T.jaM.mi(exp(n0,9))\overline{SAT} \in
Rozważ następującą grę karcianą (znaną we Włoszech jako „Cavacamicia”, którą można przetłumaczyć jako „stripshirt”): Dwóch graczy losowo dzieli na dwie talie standardową talię kart. Każdy gracz otrzymuje jedną talię. Gracze naprzemiennie umieszczają na stosie następną kartę ze swojej...
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...
Rozważmy wymiarowy wektor gdzie . Dla każdego wiemy i załóżmy, że są niezależne. Wykorzystując te prawdopodobieństwa, czy istnieje skuteczny sposób na iterację binarnych wektorów wymiarowych w kolejności od najbardziej prawdopodobnego do najmniej prawdopodobnego (z dowolnymi wyborami wiązań) z...
Odpowiadając na to pytanie w cstheory , (nieformalnie) udowodniłem w locie następujące twierdzenie: Twierdzenie : Dla dowolnego ustalonego sonda cyklu Hamiltoniana pozostaje NP-kompletna, nawet jeśli jest ograniczona do płaskich dwustronnych grafów niekierowanych o maksymalnym stopniu 3, które nie...
Właśnie ukończyłem krótki (5-stronicowy) artykuł na temat udowodnienia pewnej gry kombinatorycznej NP-Complete. Nie jest to w żaden sposób wynikiem wielkiego znaczenia, ale uważam, że można je opublikować. Jakie miejsca byłyby dobre dla takiego papieru? Jedyne, o czym wiem, to Listy przetwarzające...
Powiedzmy, że rodzina grafów ma długo indukowane ścieżki, jeśli istnieje stała ϵ > 0, tak że każdy wykres G w F zawiera ścieżkę indukowaną na | V ( G ) | ϵ wierzchołki. Interesują mnie właściwości rodzin grafów, które zapewniają istnienie długo indukowanych ścieżek. W szczególności zastanawiam...
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...
Jaka jest minimalna szerokość drzewa obwodu powyżej {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} do obliczenia MAJ? Tutaj MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} wyprowadza 1, jeśli co najmniej połowa jego danych wejściowych to 111 . Dbam tylko o rozmiar obwodu (powinien być...
Więc wszyscy znamy dolną granicę drzewa na podstawie najgorszego przypadku porównań wykonanych przez (deterministyczny) algorytm sortowania porównań. Nie dotyczy losowego sortowania porównań (jeśli mierzymy oczekiwane porównania dla danych wejściowych w najgorszym przypadku). Na przykład, dla ,...