Teoretyczne informatyka

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

4
Jakie są różnice między relacjami logicznymi a symulacjami?
Jestem początkującym pracującym nad metodami potwierdzającymi równoważność programu. Przeczytałem kilka artykułów na temat definiowania relacji logicznych lub symulacji, aby udowodnić, że dwa programy są równoważne. Ale jestem dość zdezorientowany co do tych dwóch technik. Wiem tylko, że relacje logiczne są definiowane indukcyjnie, podczas gdy symulacje oparte są na koindukcji. Dlaczego …
19
Piękne wyniki w TCS
Niedawno mój przyjaciel (pracujący w TCS) wspomniał w rozmowie, że „chciał zobaczyć / poznać wszystkie (lub jak najwięcej) pięknych wyników w TCS w swoim życiu”. Ten rodzaj sprawił, że zastanawiałem się nad pięknymi wynikami w tej dziedzinie, a tym samym motywacją do następującego pytania: Które wyniki (lub pomysły) są Twoim …
3
Co rozumiemy przez heurystyczne argumenty fizyki statystycznej?
Słyszałem, że w fizyce statystycznej istnieją heurystyczne argumenty, które dają wyniki w teorii prawdopodobieństwa, dla których rygorystyczne dowody są albo nieznane, albo bardzo trudne do uzyskania. Jaki jest prosty zabawkowy przykład takiego zjawiska? Byłoby dobrze, gdyby odpowiedź obejmowała niewielkie podstawy fizyki statystycznej i mogła wyjaśnić, czym są te tajemnicze heurystyki …
4
Czy probabilistyczna maszyna Turinga może rozwiązać problem zatrzymania?
Komputer z nieskończonym strumieniem naprawdę losowych bitów jest potężniejszy niż komputer bez niego. Pytanie brzmi: czy jest wystarczająco silny, aby rozwiązać problem zatrzymania? Czy komputer probabilistyczny może ustalić, czy program deterministyczny przestaje działać? Przykład, w którym komputer probabilistyczny robi coś, czego deterministycznie nie można: Rozważmy mały program (o długości mniejszej …
7
Udowadnianie dolnych granic przez udowodnienie górnych granic
Niedawny wynik Ryana Williamsa w przełomowym złożoności obwodu w dolnej granicy zapewnia technikę dowodową, która wykorzystuje wynik górnej granicy w celu udowodnienia niższych granic złożoności. Suresh Venkat w swojej odpowiedzi na to pytanie: Czy są jakieś sprzeczne z intuicją wyniki w informatyce teoretycznej? , podał dwa przykłady ustanawiania dolnych granic …
3
Curry-Howard i programy z niekonstruktywnych dowodów
To jest kolejne pytanie do Jaka jest różnica między dowodami a programami (lub między propozycjami i typami)? Jaki program odpowiadałby niekonstruktywnemu (klasycznemu) dowodowi formy ? (Załóżmy, że jest interesującą zależnością rozstrzygalną, np. ta TM nie zatrzymuje się w krokach ).∀k T(e,k)∨¬∀k T(e,k)∀k T.(mi,k)∨¬∀k T.(mi,k)\forall k \ T(e,k) \lor \lnot \forall …
1
Funkcje, które nie są wydajnie obliczalne, ale można się ich nauczyć
Wiemy, że (patrz np. Twierdzenia 1 i 3 z [1]), z grubsza mówiąc, w odpowiednich warunkach, funkcje, które mogą być skutecznie obliczone przez maszynę Turinga w czasie wielomianowym („wydajnie obliczalne”), mogą być wyrażone przez wielomianowe sieci neuronowe z rozsądnymi rozmiarami, a zatem można się go nauczyć z wielomianową złożonością próbki …
2
Czy nie możemy przedstawić złożoności Kołmogorowa?
Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga UUU która na wejściu (T,x)(T,x)(T,x) (zakodowana jako kod bez prefiksu TTT a następnie xxx ) wyprowadza dowolne TTT na wejściu xxx (ewentualnie oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla xxx , K(x)K(x)K(x) , jako długość najkrótszego programu ppp tak aby …
2
Jakich funkcji nie może obliczyć System F?
W tym artykule na Wikipedii o kompletności Turinga stwierdza się, że: Rachunek lambda bez typu jest zakończony przez Turinga, ale wiele typowych rachunków lambda, w tym System F, nie jest. Wartość typowanych systemów polega na ich zdolności do reprezentowania najbardziej typowych programów komputerowych przy wykrywaniu większej liczby błędów. Jaki jest …
6
Naturalne problemy NP-zupełne z „dużymi” świadkami
Pytanie dotyczące teorii „ Co to jest NP ograniczony do świadków wielkości liniowej? ” Dotyczy klasy NP ograniczonej do świadków wielkości liniowej , aleO ( n )O(n)O(n) Czy istnieją naturalne problemy NP-zupełne, w których (tak) przypadki wielkości wymagają świadków o rozmiarze większym niż n ?nnnnnn Oczywiście możemy budować sztuczne problemy, …
1
Czy jednolity RNC jest zawarty w przestrzeni polilogu?
Logarytmiczna jednolita NC jest zawarta w deterministycznej przestrzeni polilogu (czasami zapisywanej jako PolyL). Czy RNC o jednolitej przestrzeni logów również należy do tej klasy? Standardowa losowa wersja PolyL powinna być w PolyL, ale nie widzę, aby (jednolity) RNC był w randomizowanym-PolyL. Trudność, jaką widzę, polega na tym, że w RNC …
4
Problemy „ukierunkowane”, które są łatwiejsze niż ich wariant „niekierowany”.
Prezentowałem wykład na temat sortowania naleśników i wspomniałem, że: Sortowanie według zamian jest trudne „podpisany” sortując odwrócenia jest w P . Co skłoniło mnie do myślenia. W pewnym sensie sortowanie „sygnowane” jest „ukierunkowane” - możesz postrzegać znak jako kierunek (i rzeczywiście jest to motywacja z biologii ewolucyjnej). Ale to łatwiejszy …
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.