Teoretyczne informatyka

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

2
NTIME (n ^ k) ≠ DTIME (n ^ k)?
W „O determinizmie kontra niedeterminizm i pokrewnych problemach” (Proc. IEEE FOCS, strony 429–438, 1983) Paul, Pippenger, Szemerédi i Trotter udowodnili, że . N T I M E ( n ) ≠ D T I M E ( n )NTIME(n)≠DTIME(n)\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n) Odpowiada to na moje pytanie przy k = 1. Czy coś …
2
Konsekwencje
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” (Bennett i in. 1997): jeśli odrzucisz strukturę problemu i po prostu weźmiesz …
1
vs?
Centralnym problemem teorii złożoności jest zapewne vs .P.PPN.P.NPNP Ponieważ natura jest kwantowa, bardziej naturalne wydaje się rozważenie klas (tj. Problemów decyzyjnych rozwiązanych przez komputer kwantowy w czasie wielomianowym, z prawdopodobieństwem błędu co najwyżej 1/3 dla wszystkich instancji) i (ekwiwalent kwantowy z ) zamiast.B Q PBQPBQPQ MZAQMAQMAN.P.NPNP Moje pytania: 1) Czy …
6
Wydajne i proste randomizowane algorytmy, w których determinizm jest trudny
Często słyszę, że w przypadku wielu problemów znamy bardzo eleganckie algorytmy randomizowane, ale nie ma, lub tylko bardziej skomplikowane, deterministyczne rozwiązania. Znam jednak tylko kilka przykładów. Najbardziej widoczne Randomized Quicksort (i powiązane algorytmy geometryczne, np. Dla wypukłych kadłubów) Randomized Mincut Testowanie tożsamości wielomianowej Problem Klee'a Spośród nich jedynie testowanie tożsamości …
2
Status światów Impagliazzo?
W 1995 r. Russell Impagliazzo zaproponował pięć światów złożoności: 1- Algorytmika: ze wszystkimi niesamowitymi konsekwencjami.P.= NP.P.=N.P.P=NP 2- Heuristica: problemy kompletne są trudne w najgorszym przypadku ( ), ale można je skutecznie rozwiązać w przeciętnym przypadku.N.P.N.P.NPP.≠ N.P.P.≠N.P.P \ne NP 3- Pessiland: Występują problemy z niepełną średniej wielkości przypadków , ale funkcje …
2
W jaki sposób TCS stał się zorientowany na konferencję, a nie na czasopismo?
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 następnej konferencji. Czasami pojawia się wersja dziennika. Czasem tak nie …
4
Dlaczego ktoś miałby używać Octree zamiast drzewa KD?
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 ustalonych regularnych odstępach czasu, z tego, co zbieram. Trochę badań dotyczących niezależności wydaje …
7
Soczewka algorytmiczna w naukach społecznych
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 informacji, a AI i teoria złożoności wydają się regularnie oddziaływać z neuronauką. Nauki …
3
Założenia antologii złożoności
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ń, albo hipotezy losowej wyroczni. Najważniejszym i powszechnie uznawanym założeniem jest to, …
1
Czy LOGLOG = NLOGLOG?
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 niedeterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). …
14
Książka o prawdopodobieństwie
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 prawdopodobieństwa i bardzo łatwo dowodzą twierdzeń; podczas gdy muszę spędzić …
4
Twardość aproksymacji przy założeniu NP! = CoNP
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 coNPAAAAAAαα\alphaNP=coNPNP=coNPNP = coNP Wiadomym jest, że „pokazuje współczynnik NP twardość najkrótszym problemu wektora …
5
Języki programowania dla wydajnych obliczeń
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ć język, w którym możemy wyrazić wszystkie wydajne obliczenia i tylko wydajne obliczenia. Na …
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.