Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Rozkłady grafów do łączenia „lokalnych” funkcji etykietowania wierzchołków
∑x∏i j ∈ Efa( xja, xjot)∑x∏jajot∈mifa(xja,xjot)\sum_x \prod_{ij \in E} f(x_i,x_j)maxx∏i j ∈ Efa( xja, xjot)maxx∏jajot∈mifa(xja,xjot)\max_x \prod_{ij \in E} f(x_i,x_j) Gdzie Max lub suma przejmuje wszystkie labelings z , produkt wprowadza się na wszystkie krawędzie dla grafu G = \ {V, E \} i f jest dowolną funkcją. Ilość ta jest …
2
Algorytmy SC ^ 2 dla łączności st
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 …
2
Trudne problemy NP na grafach ekspanderów?
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ć taki wynik dla -hard problemu?NPNPNP
1
Rzadka transformacja Walsha-Hadamarda
Walsh-Hadamard'a transformacji (BLK) jest uogólnieniem transformaty Fouriera i jest prostopadła do przetwarzania na wektorze rzeczywistych lub liczb zespolonych o wymiarze . Transformacja jest popularna w obliczeniach kwantowych, ale ostatnio badano ją jako rodzaj warunku wstępnego losowych rzutów wektorów wielowymiarowych do wykorzystania w dowodzie lematu Johnsona-Lindenstraussa. Jego główną cechą jest to, …
2
Czy istnieją pośrednie teorie eta dla rachunku lambda?
Istnieją dwie główne, zbadane teorie rachunku lambda, teorii beta i jej rozwinięcia post-zupełnego, teorii beta-eta. Czy te dwie teorie mają pośrednią, rodzaj pośredniej reguły eta, która daje spójną teorię przepisywania? Czy istnieje jakieś interesujące pojęcie częściowej ekstensywności, któremu ono odpowiada? Jest to drugie pytanie, które zadałem w ramach pośredniej eta, …
1
Czy dowody, że permanent nie jest w mundurze
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 też używają czegoś więcej niż zwykła diagonalizacja. Więc …
3
Czy są jakieś klasy funkcji, które wymagają obliczalnie różnych zasobów do obliczenia w porównaniu do obliczenia ich odwrotności?
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 iniekcyjny fn(x)fn(x)f_n(x) jest przejmujący fn(x)fn(x)f_n(x) zajmuje znacznie mniej zasobów (albo przestrzeń / czas / głębokość obwodu …
6
Globalne właściwości klas dziedzicznych?
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 wykazał, że dla klas grafów z wyłączeniem drobnych istnieje algorytm wielomianowy dla izomorfizmu, …
1
Czy dolna granica dowodu w tym dokumencie jest poprawna?
W tym artykule Erika D. Demaine'a, Sandora P. Fekete, Roberta J. Langa na stronie 15, ryc. 13, „Opakowanie w koło do projektowania origami jest trudne”, twierdzą, że długość boku najmniejszego kwadratu obejmującego dwa koła każdy z obszaru 1/2 wynosi 1,471299. Z moich obliczeń wynika, że ​​długość boku wynosi 1,362 i …
2
Eliminowanie cofix w dowodzie Coq
Próbując udowodnić pewne podstawowe właściwości przy użyciu typów koindukcyjnych w Coq, ciągle napotykam na następujący problem i nie mogę go obejść. Wydzieliłem problem na prosty skrypt Coq w następujący sposób. Rodzaj Drzewo definiuje ewentualnie nieskończone drzew z gałęziami oznaczonych elementów typu A . Oddział nie musi być określone dla wszystkich …
10
Nieprzerwalność problemów NP-zupełnych jako zasada fizyki?
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 konsekwencji dla świata fizycznego istnienia nierozwiązywalnych problemów (lub istnienia …
2
Czy APX jest zawarty w NP?
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, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.