Teoretyczne informatyka

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

1
Jak dobry może być detektor zatrzymania?
Czy istnieje Maszyna Turinga, która może zadecydować, czy prawie wszystkie inne Maszyny Turinga zatrzymają się? Załóżmy, że mamy jakieś wyliczenie maszyn Turinga i pewne pojęcie o „rozmiarze” zbioru liczb naturalnych, a my definiujemy:N →{ Mja}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥ ⋅∥‖⋅‖\| \cdot \| fa( i ) = ∥ { n : Mja nie …
1
Entropia i złożoność obliczeniowa
Są badacze wykazujący, że bit wymazywania musi zużywać energię, czy teraz są jakieś badania dotyczące średniego zużycia energii algorytmu o złożoności obliczeniowej ? Wydaje mi się, że złożoność obliczeniowa F ( n ) jest skorelowana ze średnim zużyciem energii, mam nadzieję, że mogę tu znaleźć odpowiedź.F(n)F(n)F(n)F(n)F(n)F(n)
1
Sortuje
W ostatnim przedruku https://arxiv.org/abs/1801.00776 twierdzi się, że liczb rzeczywistych można posortować w czasie O ( n √nnn i przestrzeń liniowa. Artykuł wydaje się rozsądny, chociaż nie jestem ekspertem w dziedzinie algorytmów sortowania.O(nlogn−−−−√),O(nlog⁡n),O(n \sqrt{\log n}), Jeśli jest poprawny, byłoby to, moim zdaniem, znaczące, przynajmniej teoretycznie. Przedstawienie głównego argumentu jest jednak nieco …
1
Zwykły język, który rozróżnia dwa deterministyczne CFG
Załóżmy, że masz dwa deterministyczne automaty wypychające, które rozpoznają języki i B , i chcesz ustalić, czy istnieje regularny język R, taki jak A ⊆ R i R ∩ B = ∅ . Zasadniczo wyzwanie polega na ustaleniu, czy istnieje DFA, który może rozpoznać, który z dwóch języków pochodzi z …
1
Złożoność testowania, jeśli dwa zestawy
Wyobraźmy sobie, że mamy dwa zestawy rozmiarów punktów . Jaka jest (czasowa) złożoność testowania, jeśli różnią się one tylko rotacją? : istnieje macierz rotacji taka, że ?mmmX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Istnieje tutaj problem reprezentowania rzeczywistych wartości - dla uproszczenia załóżmy, że dla każdej współrzędnej istnieje (krótki) wzór algebraiczny, tak że koszt podstawowych …
1
Pierwotne źródło równoważności niedeterministycznej weryfikacji wielomianu i deterministycznej weryfikacji czasu wielomianu
Kto jako pierwszy pokazał, że dany język jest w NP, jeśli certyfikat dla tego języka można zweryfikować w czasie wielomianowym? Czy mamy dokument, który formalnie to potwierdza? Kiedy społeczność TCS zaczęła kłaść nacisk na niedeterminizm na rzecz weryfikowalności? Nie mogę znaleźć dla tego dobrego odniesienia poza tekstami takimi jak Papadimitriou, …
1
Kompresowanie informacji o problemie zatrzymania w maszynach wyroczni Turinga
Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia. Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź na problem zatrzymania dla wszystkich 2 n - 1 maszyn Turinga, przy …
1
Hierarchie czasu w DSPACE (O (s)))
Twierdzenie o hierarchii czasu stwierdza, że ​​maszyny Turinga mogą rozwiązać więcej problemów, jeśli mają (wystarczająco) więcej czasu. Czy to w jakiś sposób się utrzymuje, jeśli przestrzeń jest asymptotycznie ograniczona? Jak DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) odnosi się do DTISP(f(n),O(s(n)))DTISP(f(n),O(s(n)))\textrm{DTISP}(f(n), O(s(n))) jeśli fgfg\frac{f}{g} rośnie wystarczająco szybko? Ja szczególnie zainteresowany w przypadku, s(n)=ns(n)=ns(n) = n …
3
Dlaczego informatycy w ogóle pracują przy założeniu, że P ≠ NP?
Jadąc od tła matematyki, wydaje mi się, że interesujący na całego komputera naukowcy mają tendencję do pracy przy założeniu, że P≠NPP≠NPP \neq NP . Chociaż nie ma żadnego dowodu w obu przypadkach, chyba że coś może być szczególnie niepotwierdzone zarówno w matematyce, jak i nauce, jest podejmowane z dużą ilością …
12 p-vs-np 
2
Euklidesowy TSP w NP i złożoność pierwiastka kwadratowego
W notatkach z wykładu Oli Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf mówi się, że nie wiemy, czy Euclidean TSP jest w NP: Powodem jest to, że nie wiemy, jak skutecznie obliczać pierwiastki kwadratowe. Z drugiej strony jest ten artykuł Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123, który mówi, że jest NP-kompletny, co oznacza również, że jest w NP. Chociaż …
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.