Teoretyczne informatyka

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

4
Pozytywne uporządkowanie topologiczne, weź 3
Załóżmy, że mamy macierz n na n. Czy można zmienić kolejność wierszy i kolumn, tak aby uzyskać matrycę górnego trójkąta? To pytanie jest motywowane tym problemem: Pozytywne uporządkowanie topologiczne Pierwotny problem decyzyjny jest co najmniej tak trudny jak ten, więc wynik kompletności NP również by go rozwiązał. Edycja: Laszlo Vegh …
5
Kontrola wersji do współpracy (z różnicami na poziomie słów)?
Większość prac jest teraz pisanych wspólnie, a współpracownicy często znajdują się w różnych miejscach. Zawsze używałem systemów kontroli wersji dla moich dokumentów i kodu, a także uważałem kontrolę wersji za kluczową dla wspólnych projektów oprogramowania, ale wydaje się, że wielu badaczy teoretycznie unika ich użycia do pisania wspólnych dokumentów. Aby …
1
Czy wszystkie klasy złożoności mają charakterystykę języka liścia?
Języki liścia są pięknym sposobem na jednolite zdefiniowanie wielu klas złożoności. Większość klas złożoności jest zwykle określana przez model obliczeniowy (np. Deterministyczna / losowa TM) i związany z zasobami (czas dziennika, przestrzeń wielopunktowa itp.). Jednak w sformułowaniu języka liścia istnieje tylko jeden model obliczeń, a klasa jest określona przez podanie …
4
Czy istnieje odpowiednik derandomizacji dla algorytmów kwantowych?
W przypadku niektórych algorytmów randomizowanych można go zdemandomizować, usuwając (przy możliwym koszcie w czasie wykonywania) użycie bitów losowych i maksymalizując pewną dolną granicę celu (zwykle obliczaną na podstawie faktu, że twierdzenia dotyczą oczekiwanej wydajności losowej algorytm). Czy istnieje odpowiednik algorytmów kwantowych? Czy są jakieś dobrze znane wyniki „dekwantyzacji”? A może …
2
normalne zachowanie maszyn Turinga
Czytając kilka ostatnich wątków na temat obliczeń kwantowych ( tutaj , tutaj i tutaj ), pamiętam interesujące pytanie o moc jakiegoś rodzaju maszyny do zachowania normalnego zachowania.ℓpℓp\ell_p Dla osób pracujących w teorii złożoności, które dążą do złożoności kwantowej, doskonałym tekstem wprowadzającym jest praca Fortnowa, której link zamieścił tutaj Joshua Grochow …
2
Szacowanie średniej w czasie wielomianowym
Niech f:{0,1}n→(2−n,1]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1] będzie funkcją. Chcemy oszacować średnią fff ; to znaczy: E[f(n)]=2−n∑x∈{0,1}nf(x)E[f(n)]=2−n∑x∈{0,1}nf(x)\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x) . NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if …
3
Czy możliwe są rekurencyjne formy wypowiedzi Godela?
Samoreferencyjność problemu P / NP była czasem podkreślana jako bariera dla jego rozwiązania, patrz na przykład artykuł Scotta Aaronsona, czy P vs. NP jest formalnie niezależny ? Jednym z wielu możliwych rozwiązań P / NP byłby dowód, że problem jest formalnie niezależny od ZFC lub prawdziwy, ale niemożliwy do udowodnienia. …
3
Testowanie właściwości w innych metrykach?
Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R fff jest członkiem pewnej klasy funkcjiCC\mathcal{C} fff jest -far z każdej funkcji w klasie .εε\varepsilonCC\mathcal{C} Zakres funkcji jest czasem wartością logiczną: , ale nie …
3
kosmiczne bazy TM i wyrocznie
Zasadniczo taśma zapytania dla wyroczni liczy się do złożoności przestrzennej bazy TM. Wydaje się jednak prawdopodobne, aby zezwolić na taśmę Oracle tylko do zapisu (na przykład w przypadku redukcji przestrzeni L). Czy taka konstrukcja jest przydatna? Czy przynosi jakieś absurdalne wyniki?
3
Jaki jest właściwy model teoretyczny do projektowania algorytmów dla obecnych i przyszłych komputerów o wysokiej wydajności
To pytanie jest podobne do bardziej ogólnego pytania dotyczącego tego, jaki jest właściwy model teoretyczny komputera do projektowania algorytmów i struktur danych. Tutaj pytam konkretnie o obecne komputery o wysokiej wydajności (takie jak te wymienione na liście 500 najlepszych ), a nawet o nadchodzące superkomputery. Biorąc pod uwagę, że komputery …
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.