Szukam: Michael O. Rabin, „Stopień trudności obliczenia funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”, Uniwersytet Hebrajski, Jerozolima, 1960 Streszczenie: „Próbujemy zmierzyć ilość pracy związanej z obliczeniem danej funkcji obliczeniowej (rekurencyjnej). Wprowadzono i zbadano...
Lance Fortnow stwierdził ostatnio, że udowodnienie L! = NP powinno być łatwiejsze niż udowodnienie P! = NP : Oddziel NP od przestrzeni logarytmicznej. Podałem cztery podejścia w ankiecie przeprowadzonej przed blogiem w 2001 r. Na temat diagonalizacji (sekcja 3), chociaż żadna z nich się nie...
Klasa złożoności PPAD została wynaleziona przez Christosa Papadimitriou w jego przełomowym artykule z 1994 roku . Klasa ma na celu uchwycenie złożoności problemów wyszukiwania, w których istnienie rozwiązania jest gwarantowane przez „Argument parzystości w grafach ukierunkowanych”: jeśli w grafie...
Adleman wykazały w 1978 r : Jeżeli logiczna funkcja o zmiennych może być obliczany za pomocą prawdopodobieństwa logicznego obwodu o rozmiarze , a następnie może być obliczany za pomocą deterministycznych obwód boolowski wielomianu wielkości w i ; właściwie o wielkości ....
Załóżmy, że mamy właściwość grafu, którą można sprawdzić w niedeterministycznym czasie wielomianowym, oraz dowód w słabym systemie formalnym (powiedzmy RCA 0 ), że właściwość jest nieznacznie zamknięta. Czy możemy powiedzieć coś o sile systemu formalnego, który jest w stanie udowodnić, że dany...
Biorąc pod uwagę skończony (deterministyczny lub niedeterministyczny, nie sądzę, że ma to duże znaczenie) automat A i próg n , czy A akceptuje słowo zawierające najwyżej n odrębnych liter? (Przez k różnych liter rozumiem, że aabaa ma dwie różne litery, a i b .) Pokazałem, że ten problem jest...
Rozważ następującą grę na ukierunkowanym wykresie ważonym solGG z chipem w pewnym węźle. Wszystkie węzły solGG oznaczone są literą A lub B. Jest dwóch graczy Alice i Bob. Celem Alicji (Bob) jest przesunięcie czipa do węzła oznaczonego literą A (B). Początkowo Alice i Bob mają odpowiednio...
Jakie inne problemy występują w językach innych niż izomorfizm grafów w ? Czy możesz podać jakieś referencje?NP∩coAMNP∩coAMNP\cap coAM Aktualizacja: Zapomniałem wspomnieć, że jestem zainteresowany w językach nie wiadomo, że w
Niech { 0 , . . . , N - 1 }, a ∘ : S x S → S . Chcę obliczyć złożoność komunikacji przy podejmowaniu decyzji, czy ∘ jest skojarzone.S=S=S=0,...,n−10,...,n−10,...,n-1∘:S×S→S∘:S×S→S\circ : S \times S \rightarrow S∘∘\circ Model jest następujący. podano jako matrycy M . Alice (lub. Bob) otrzymuje...
Papier Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre...
Równoważna kompozycja PCF twierdzenie jest: max dla 3-SAT jest -hard odróżnić spe wzorów i wzorach w których co najwyżej r -fraction z klauzul spe (jakiegoś R < 1 ).N.P.NPNPrrrr < 1r<1r\lt 1 Czy istnieje znane twierdzenie o dychotomii, które klasyfikuje wszystkie Max CSP na podstawie...
W poniższym pytaniu wykorzystano pomysły z kryptografii zastosowane w teorii złożoności. To powiedziawszy, jest to pytanie teoretycznie złożone, i aby odpowiedzieć na to pytanie, nie jest wymagana żadna wiedza kryptograficzna. Celowo piszę to pytanie bardzo nieformalnie. Brakuje szczegółów,...
Przez http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Jeśli jest językiem PSPACE uzupełniania, P = N P A .AAAPA=NPAPA=NPAP^{A}=NP^{A} Jeśli jest deterministyczną wyrocznią wielomianową, P B ≠ N P B (przy założeniu P ≠ N P ).BBBPB≠NPBPB≠NPBP^{B}\ne NP^{B}P≠NPP≠NPP\ne NP to klasa...
Znów problem podziału krawędzi, którego złożoność jestem ciekawy, motywowany moim poprzednim pytaniem . Dane wejściowe: wykres sześciennyG=(V,E)G=(V,E)G=(V,E) Pytanie: czy istnieje podział na , taki że podgrupa indukowana przez każdy jest albo pazurem (tj. , często nazywanym gwiazdą), albo...
Wynik Baker-Gill-Solovay wykazał, że pytanie P = NP nie relatywizuje, w tym sensie, że żaden dowód relatywizacyjny (niewrażliwy na obecność wyroczni) nie może rozstrzygnąć pytania P = NP. Moje pytanie brzmi: czy istnieje podobny wynik pytania: „Czy istnieje problem z pełnym PH?” Odpowiedź...
Zastanawiam się konkretnie, czy istnieje interesujący warunek dotyczący odsetka zadań spełniających formułę 3SAT, aby zagwarantować, że takie problemy są możliwe do rozwiązania. Załóżmy na przykład, że klasa problemów 3SAT z 2 n możliwych przypisań spełnia wzór logiczny; czy możemy skutecznie...
Pracując nad nieco niezwiązanym projektem dla Suresh, ostatnio natknąłem się na pracę wykonaną przez Page i Opper na temat systemów tworzonych przez użytkowników, a część ich pracy krótko omówiła problemy, których nie można zweryfikować w czasie wielomianowym. Nie udało mi się znaleźć wielu...
Zliczając argumenty, można pokazać, że istnieją wielomiany stopnia n w 1 zmiennej (tj. Coś w postaci które mają złożoność obwodu n. Można również pokazać, że wielomian taki jak wymaga co najmniej mnożenia (potrzebujesz tego tylko, aby uzyskać wystarczająco wysoki stopień). Czy są jakieś wyraźne...
Niech G będzie połączonym wykresem. Jaka jest złożoność zliczania wszystkich połączonych podgrafów, jeśli G jest następujących typów? G jest ogólny. G jest planarne. G jest dwustronny. Nie dbam o żadne struktury lub ..., po prostu muszę policzyć wszystkie połączone podgrupy!...
Niedawno przypomniano mi o problemie vs. jak wyjaśnił Stephen A. Cook z Clay Mathematics Institute.N PP.P.\mathsf{P}N P.N.P.\mathsf{NP} To wzbudziło moje zainteresowanie i chciałbym dowiedzieć się więcej na ten temat. Pierwszym krokiem byłoby lepsze zrozumienie problemu i ogólne zrozumienie tego...