Interesuje mnie pytanie, czy NP jest równy coNP, czy nie. Byłbym wdzięczny za porady dotyczące dobrych publikacji do przeczytania na ten temat. Dla przypomnienia, wiem, że to pytanie jest ściśle związane z pytaniem, czy P jest równe NP, czy nie (takie, że jeśli NP! = CoNP, to P! = NP). Na...
Niektóre tło: Chciałbym znaleźć „mniej znane” dolne granice (lub wyniki twardości) dla problemu Uczenie się z błędami (LWE) i ich uogólnienia, takie jak Uczenie się z błędami przez pierścienie. W celu uzyskania szczegółowych definicji itp. Oto miła ankieta przeprowadzona przez Regev:...
Bardzo interesującym otwartym problemem w badaniu miar złożoności funkcji boolowskiej jest tak zwana hipoteza wrażliwości vs. blokowa. Informacje na temat wrażliwości kontra czułości bloków można znaleźć na następującym blogu S. Aaronsona na stronie http://www.scottaaronson.com/blog/?p=453...
Czy ta doskonała gra informacyjna rozgrywana na wykresach jest znana / studiowana? Biorąc pod uwagę wykres G=(V,E)G=(V,E)G= (V,E) , dwóch graczy na przemian wybiera krawędź lub izolowany węzeł. Jeśli gracz wybierze krawędź e=(u,v)e=(u,v)e = (u,v) dwa węzły uuu i vvv zostaną usunięte wraz ze...
Próbuję zrozumieć protokół bitcoin w kontekście obliczeniowych zabezpieczeń kryptograficznych. Pytanie dotyczy prośby o odniesienie do podstaw artykułów z kryptografii na bitcoinach. Moje pierwsze pytanie brzmi: jaki bitcoin abstrakcyjnego protokołu kryptograficznego próbuje wdrożyć? Czy mamy...
Częścią trudności w znalezieniu więcej informacji na temat tego problemu jest to, że problem z dopasowaniem wykresu różni się od jego znacznie bardziej znanego kuzyna, problemu z dopasowywaniem, ale trudno go od niego odróżnić podczas korzystania z wyszukiwarek. Biorąc pod uwagę dwa wykresy i...
Do tej pory istnieje mnóstwo wyników dotyczących separatorów na wykresach, od płaskiego separatora, separatora drzew, ograniczonych wykresów szerokości drzewa, ograniczonych wykresów rodzajów itp. Itp. Czy jest jakaś dobra zaktualizowana ankieta na ten temat i ich
Jestem zainteresowany badaniem kompletnych problemów z Graph Isomorphism (GI). W artykule „Problemy wielomianowo równoważne z izomorfizmem grafowym” Kellogga S. Bootha (1979) udowodnili, że wiele podstawowych problemów jest uzupełnionych GI przy użyciu technik zastępowania krawędzi, technik...
Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji...
Szukam zasobów (najlepiej podręcznika) na zaawansowane tematy w algorytmach (tematy wykraczające poza to, co są omówione w podręcznikach algorytmów, takich jak CLRS i DPV). Rodzaj materiału, który można wykorzystać do nauczania tematów w kursie algorytmów, takich jak Erik Demaine i kurs Davida...
Czy znasz problemy, które są twarde W [1], nawet w przypadku wykresów o ograniczonym stopniu? Wymiar metryczny jest trudny na wykresach ze stopniem co najwyżej 3, ale ma twardość W [2]. Czerwono-niebieski Nonblocker był twardy W [1] na wykresach ze stopniem ograniczonym, ale wystąpił błąd w...
Czy znane jest następujące roszczenie? Twierdzenie : Dla każdego wykresu z wierzchołkami istnieje kolorystyka tak że każdy niezależny zestaw jest zabarwiony co najwyżej kolorami .n G O ( √solGGnnnsolGGO (
W twierdzeniach za darmo! , Wadler mówi, że charakterystykę parametryczności można wyrazić ponownie w kategoriach luźnych naturalnych przekształceń i będzie to przedmiotem kolejnego artykułu. Do którego referatu się odnosi? W znanym mi kategorycznie podejściu do paramteryczności stosuje się...
Oznacz przez minimalny stopień wyjściowy w G , a przez δ - ( G ) minimalny stopień wyjściowy.δ+(G)δ+(G)\delta^+(G)GGGδ−(G)δ−(G)\delta^-(G) W powiązanym pytaniu wspomniałem o rozszerzeniu Ghouili-Houri twierdzenia Diraca o cyklach hamiltonowskich , co sugeruje, że jeśli to G oznacza...
Rozważmy wykres (problem ma sens zarówno dla wykresów skierowanych, jak i niekierowanych). Nazwij macierzą odległości : to najkrótsza odległość ścieżki od wierzchołka do wierzchołka w dla pewnej stałej funkcji agregacji (na przykład lub ).M G G M G [ i , j ] i j G + maxsolGGM.solMGM_GsolGGM.sol[ i...
Conway ma bardzo ładną konstrukcję o surrealistycznych liczbach. Są to „liczby”, które zawierają zarówno liczby rzeczywiste, jak i liczby porządkowe, są całkowicie uporządkowane i mają wszystkie właściwości pola (z wyjątkiem, że nie tworzą zbioru, ale klasę). Zobacz na przykład ten plik pdf lub...
Rozważ następujący problem: Biorąc pod uwagę dwa ciągi x, y, zdecyduj, czy istnieje homomorfizm ciągu f taki, że f (x) = y. Łatwo jest pokazać, że problem ten jest w . Czy są inne rzeczy, które możemy powiedzieć o tym problemie? Jest to na przykład w c o N P lub nawet P...
Jak wiemy, definicja złożoności obliczeniowej algorytmu prawie nie budzi kontrowersji, ale definicja złożoności obliczeniowej rzeczywistych lub modeli obliczeniowych rzeczywistych nie jest w takim przypadku. Model i model Bluma i Smalesa znamy w książce Computable Analysis. I pozornie model w...
Chciałbym wiedzieć (związany z tym drugim pytaniem ), czy dolne granice były znane z następującego problemu testowego: jeden ma dostęp do zapytania do sekwencji liczb nieujemnych i , z obietnicą, że albo lub .an≥⋯≥a1an≥⋯≥a1a_n \geq \dots\geq a_1ε∈(0,1)ε∈(0,1)\varepsilon \in...
Jestem absolwentem informatyki teoretycznej, aw szczególności algorytmów aproksymacyjnych. Teraz uważam, że bardziej interesuje mnie czysta matematyka (mogę to powiedzieć, ponieważ wydaje mi się, że bardziej podobały mi się kursy matematyki niż kursy CS). Chciałbym zapytać, czy istnieją obszary w...