Próbuję zrozumieć złożoność funkcji wyrażanych przez bramki progowe, co doprowadziło mnie do . W szczególności interesuje mnie to, co obecnie wiadomo na temat uczenia się w T C 0 , ponieważ nie jestem ekspertem w tej dziedzinie.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 Do tej pory...
Następujący problem pojawia się na liście Aaronsona Dziesięć pół-wielkich wyzwań dla teorii obliczeń kwantowych . Jest B Q P = B P PB Q N CbQP.=bP.P.bQN.do\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} Innymi słowy, i „kwantową” część dowolnego algorytmu kwantowej być skompresowane do p o l y l o g...
Czytałem, że całkowite programowanie liniowe jest rozwiązywalne w czasie wielomianowym, jeśli liczba zmiennych jest stała, tj. N ∈ O ( 1 ) . Jeśli liczba zmiennych rośnie logarytmicznie, tj. N ∈ O ( log 2 ( N ) ) dla danych wejściowych o rozmiarze N , czy problem jest nadal możliwy do rozwiązania w...
Jakie są przykłady par klas złożoności i , żeAAABBB nie wiemy, czy , iA=BA=BA=B nie znamy też sprzecznych relatywizacji (tzn. nie znamy wyroczni i tak że i )?PPPQQQAP=BP.AP=BP.A^P = B^PZAQ≠BQAQ≠BQA^Q \ne B^Q Aby sformułować pytanie w inny sposób, jakie są wyjątki od heurystyki, że jeśli nie uda...
Zastrzeżenie: Wiem bardzo mało o teorii złożoności. Przepraszam, ale tak naprawdę nie ma sposobu, aby zadać to pytanie bez (strasznie) zwięzłego: Jakie powinny być morfizmy w „kategorii” maszyn Turinga? Jest to oczywiście subiektywne i zależy od interpretacji teorii, więc odpowiedź na to...
Mój student ostatnio zadał następujące pytanie: DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n)) \subsetneq DTIME(g(n)).h(n)h(n)h(n)DTIME(f(n))⊊DTIME(h(n))⊊DTIME(g(n))?DTIME(f(n))⊊DTIME(h(n))⊊DTIME(g(n))?DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))? Prawdopodobnie można...
Twierdzenie Savitcha pokazuje, że NSPACE(f(n))⊆DSPACE(f(n)2)NSPACE(f(n))⊆DSPACE(f(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2) dla wszystkich wystarczająco dużych funkcji fff , i udowodnienie, że jest ciasno, było otwartym problemem od dziesięcioleci . Załóżmy, że podchodzimy do...
My wiemy (teraz około 40 lat, dzięki Adleman, Bennet Gill), że włączenie BPP ⊆⊆\subseteq P / poly, i jeszcze silniejszy BPP / poli ⊆⊆\subseteq P / poli trzymaj. „/ Poly” oznacza, że pracujemy nierównomiernie (osobny obwód dla każdej długości wejściowej nnn ), podczas gdy P bez tego „/ poly”...
Jaka jest następująca odmiana na okładce zestawu jako? Biorąc pod uwagę zbiór S, zbiór C podzbiorów S i dodatnią liczbę całkowitą K, czy istnieją zestawy K w C, tak że każda para elementów S leży w jednym z wybranych podzbiorów. Uwaga: Nietrudno dostrzec, że ten problem jest NP-Complete: Biorąc...
Biorąc pod uwagę język L zdefiniowany przez maszynę Turinga, która go decyduje, czy możliwe jest algorytmiczne określenie, czy L leży w
Mówi się, że problem P występuje w APX, jeśli istnieje pewna stała c> 0, tak że istnieje algorytm aproksymacji czasu wielomianowego dla P ze współczynnikiem aproksymacji 1 + c. APX zawiera PTAS (widoczne po prostu przez wybranie dowolnej stałej c> 0) i P. Czy APX jest w NP? W szczególności,...
Dziedziczna klasa struktur (np. Wykresy) to taka, która jest zamknięta pod indukowaną podbudową, lub równoważnie, jest zamknięta pod usunięciem wierzchołków. Klasy wykresów, które wykluczają nieletnie, mają ładne właściwości, które nie zależą od konkretnej wykluczonej nieletniej. Martin Grohe...
Przepraszamy z góry, jeśli to pytanie jest zbyt proste. Zasadniczo chcę wiedzieć, czy są jakieś funkcje o następujących właściwościach:f(x)f(x)f(x) Weź na gdy domena i domena kodowa są ograniczone do ciągów bitowych. Następniefn(x)fn(x)f_n(x)f(x)f(x)f(x)nnn fn(x)fn(x)f_n(x) jest...
Jest to kontynuacja tego pytania i jest związana z tym pytaniem Shivy Kinali. Wydaje się, że dowody w tych dokumentach ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) używają twierdzeń hierarchicznych. Chcę wiedzieć, czy dowody są „ czystymi ” twierdzeniami o diagonalizacji, czy...
Zawsze intryguje mnie brak danych liczbowych z matematyki eksperymentalnej za lub przeciw pytaniu P vs NP. Podczas gdy hipoteza Riemanna zawiera pewne dowody potwierdzające weryfikację numeryczną, nie znam podobnych dowodów na pytanie P vs NP. Ponadto nie jestem świadomy żadnych bezpośrednich...
Dowody naturalne stanowią barierę dla udowodnienia niższych granic złożoności obwodu funkcji boolowskich. Nie bezpośrednio wynika, takiej bariery dla udowodnienia niższe granice na obwód złożoności. Czy jest jakiś postęp w identyfikowaniu takich barier? Czy istnieją inne bariery w ustawieniu...
W prezentacji z 2006 r. Zatytułowanej WYKRESY EKSPANDERA - CZY POZOSTAJĄ ŻADNE TAJEMNICE? Nati Linial postawił następujący otwarty problem: Które -hard obliczeniowa problemu na wykresie pozostają trudne, gdy ogranicza się do wykresów ekspandera?NPNPNP Od tego czasu postęp poczyniono udowodnić...
Savitch podał algorytm deterministyczny do rozwiązania łączności st przy użyciu przestrzeni , sugerując, że N L ⊆ D S P A C E ( log 2 n ) . Algorytm Savitcha działa w czasie . Poważnym otwartym problemem jest to, czy łączność st może zostać rozwiązana przez algorytm deterministyczny w czasie...
W artykule „ Naturalne dowody” Razborova-Rudicha , strona 6, w części, w której dyskutują, że istnieją „silne dowody dolnej granicy na modele obwodów monotonicznych ” i to, jak pasują do zdjęcia, są następujące zdania: Tutaj nie chodzi o konstruktywność - wszystkie właściwości użyte w tych...
Jest -hard znaleźć czynnik stały przybliżenie najdłuższego cyklu sześciennych Hamiltona wykresach. Sześcienne wykresy hamiltonowskie mają co najmniej dwa cykle hamiltonowskie.NPNPNP Jakie są najbardziej znane wartości górnej i dolnej granicy liczby cykli hamiltonowskich na sześciennych grafach...