Jako amator TCS czytam popularny materiał wprowadzający na temat komputerów kwantowych. Oto kilka podstawowych elementów informacji, których nauczyłem się do tej pory: Komputery kwantowe nie są znane z rozwiązywania problemów NP-zupełnych w czasie wielomianowym. „Magia kwantowa nie wystarczy”...
„Wiemy”, że nazwano na cześć Steve'a Cooka, a nazywa się Nick Pippenger. Jeśli się nie mylę, Steve Cook nazwał NC na cześć Nicka Pippengera i powiedziano mi, że jest też odwrotnie. Nie znalazłem jednak żadnego dowodu na ten ostatni fakt ani w pracy Steve'a Cooka na temat DCFL, ani w dowodzie...
Mam pewne doświadczenie w obliczeniach naukowych i intensywnie korzystałem z drzewek kd do aplikacji BSP (partycjonowanie przestrzeni binarnej). Niedawno zapoznałem się raczej z oktatami, podobną strukturą danych do partycjonowania trójwymiarowych przestrzeni euklidesowych, ale taką, która działa w...
W duchu takich ogólnych dyskusji, jak ta , otwieram ten wątek z zamiarem zebrania opinii na temat otwartych wyzwań i gorących tematów w badaniach nad językami programowania . Mam nadzieję, że dyskusja może nawet ujawnić opinie na temat przyszłości badań w językach programowania. Wierzę, że ten...
Patrzenie na pytania przez obiektyw algorytmiczny (tj. Z punktu widzenia algorytmu lub złożoności) stało się przydatne w dyscyplinach poza „standardową dziedziną” informatyki. W szczególności CS wywarł wpływ na biologię poprzez biologię obliczeniową, na fizykę poprzez kwantowe przetwarzanie...
Niemożliwe jest napisanie języka programowania, który zezwala wszystkim maszynom, które zatrzymują się na wszystkich wejściach i żadnych innych. Wydaje się jednak, że łatwo jest zdefiniować taki język programowania dla dowolnej standardowej klasy złożoności. W szczególności możemy zdefiniować...
Często cytowane jest filozoficzne uzasadnienie, by wierzyć, że P! = NP nawet bez dowodu. Inne klasy złożoności mają dowody na ich odrębność, ponieważ jeśli nie, miałyby „zaskakujące” konsekwencje (takie jak upadek hierarchii wielomianowej). Moje pytanie brzmi: jaka jest podstawa przekonania, że...
Chociaż zdałem kilka kursów z teorii prawdopodobieństwa, zarówno w szkole średniej, jak i na uniwersytecie, trudno mi czytać artykuły TCS, jeśli chodzi o prawdopodobieństwo. Wydaje się, że autorzy artykułów TCS są bardzo dobrze zaznajomieni z prawdopodobieństwem. Magicznie działają ze wzorami...
Potrzebuję skończonej książki z teorią automatów z wieloma przykładami, które mogę wykorzystać do samodzielnej nauki i przygotowania się do
Od czasu do czasu słyszałem, jak ludzie mówią o algorytmach kwantowych oraz o stanach i możliwości rozważenia wielu możliwości naraz, ale nigdy nie udało mi się przekonać kogoś do wyjaśnienia stojącego za tym modelu obliczeniowego. Żeby było jasne, nie pytam o to, jak fizycznie zbudowane są...
Czy istnieje struktura danych kolejki priorytetowej, która obsługuje następujące operacje? Wstaw (x, p) : dodaj nowy rekord x z priorytetem p StableExtractMin () : Zwraca i usuwa rekord z minimalnym priorytetem, zrywając powiązania według kolejności wstawiania . Zatem po Insert (a, 1), Insert...
Dwa typowe założenia potwierdzające twardość wyników aproksymacji to i Unique Games Conjecture. Czy jest jakaś twardość wyników aproksymacji przy założeniu, że ? Szukam problemu takiego, że „trudno jest zbliżyć do współczynnika chyba że ”.P≠NPP≠NPP \neq NPNP≠coNPNP≠coNPNP \neq...
Zdefiniuj LOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (loglog n) przez deterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). Podobnie zdefiniuj NLOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (log log n) przez...
Zastrzeżenie: Mogę ręczyć tylko za moje dziedziny badań, a mianowicie metody formalne, semantykę i teorię języka programowania. Sytuacja jest prawdopodobnie inna w innych częściach dyscypliny. Wygląda na to, że TCS stało się raczej zorientowane na konferencję. Naukowcy zamierzają opublikować na...
W artykule Losowa hipoteza Oracle jest fałszywa , autorzy (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan i Rohatgi) omawiają implikacje hipotezy losowo-wyroczni . Twierdzą, że niewiele wiemy o separacjach między klasami złożoności, a większość wyników wymaga albo przyjęcia rozsądnych założeń,...
W tym pytaniu formuła 3CNF oznacza formułę CNF, w której każda klauzula obejmuje dokładnie trzy różne zmienne. Dla stałych 0 < s <1, Gap-3SAT s stanowi następujący problem: GAP 3SAT s wystąpienia : a 3CNF wzór φ. Tak, obietnica : φ jest satysfakcjonująca. No-obietnica : Brak przypisania...
To pytanie dotyczy problemów, dla których istnieje duża otwarta luka złożoności między znaną dolną i górną granicą, ale nie z powodu otwartych problemów dotyczących samych klas złożoności. Mówiąc ściślej, powiedzmy, że problem ma klasy przerw (z A ⊆ B , nie jednoznacznie zdefiniowane), jeśli A...
Czy istnieje odwrotna granica Chernoffa, która ogranicza, że prawdopodobieństwo ogona jest co najmniej tak duże. tj. jeśli X 1 , X 2 , … , X nX1,X2,…,XnX_1,X_2,\ldots,X_n są niezależnymi dwumianowymi zmiennymi losowymi, a μ = E [ ∑ n i = 1 X i ]μ=E[∑ni=1Xi]\mu=\mathbb{E}[\sum_{i=1}^n X_i] . Czy...
Pomyślałem, że podzielę się tym pytaniem, ponieważ może być interesujące dla innych użytkowników tutaj. Załóżmy, że funkcja, która jest klasą jednolitej (jak ) jest także w niewielkim klasy nierównomierne (jak A C 0 / P O l y , czyli niejednolity C 0 ), czy to oznacza, że funkcja ta jest zawarta w...
Jestem raczej zdezorientowany literaturą o ciągłej optymalizacji i literaturą TCS o tym, które rodzaje (ciągłych) programów matematycznych (MP) można skutecznie rozwiązać, a które nie. Wydaje się, że społeczność ciągłej optymalizacji twierdzi, że wszystkie programy wypukłe można skutecznie...