Teoretyczne informatyka

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

1
Interesujące algorytmy w formalizacji twierdzenia Feit-Thompson?
Wygląda na to, że George Gonthier i jego współpracownicy zakończyli formalizację Twierdzenia o nieparzystym porządku . We wcześniejszej pracy nad twierdzeniem o czterech kolorach Gonthier wynalazł szereg nowych algorytmów (głównie wariantów BDD i algorytmów grafowych), które były szczególnie podatne na formalną weryfikację. Ponieważ powiedział, że nadal stosuje ten weryfikacyjny styl …
1
Kto pierwszy zaproponował użycie
Jestem pewien, że wszyscy wiedzą o eksperymencie igły Buffona w XVIII wieku, który jest jednym z pierwszych algorytmów probabilistycznych do obliczeniaππ\pi. Implementacja algorytmu w komputerach zwykle wymaga użycia ππ\pilub funkcja trygonometryczna, która nawet jeśli są zaimplementowane jako skrócone serie, to w pewnym sensie nie udaje się to osiągnąć. Aby obejść …
3
Zwięzłe problemy w
Badanie KRÓTKI reprezentacją wykresów został zainicjowany przez Galperin i Wigderson w artykule z 1983 r, gdzie wykazać, że przez wiele problemów, takich jak proste znalezienie trójkąta na wykresie odpowiadający zwięzły wersji w -Complete. Papadimitriou i Yanakkakis ponadto ta linia badania i dowodzą, że w przypadku problemów Õ który jest N …
2
Jakie są konsekwencje ?
Shiva Kintali właśnie ogłosił (zimne!) Co powoduje, że izomorfizm wykres dla ograniczonych wykresach treewidth szerokości IS -hard≥4≥4\geq 4⊕L⊕L\oplus L . Nieformalnie moje pytanie brzmi: „Jak trudne to jest?” Wiemy, że nierównomiernie , patrz odpowiedzi na to pytanie . Wiemy również, że jest mało prawdopodobne, aby , zobaczył odpowiedzi na to …
4
Jak znaleźć cykle, które razem obejmują największą liczbę nieudostępnionych krawędzi na ukierunkowanym wykresie?
Nie jestem teoretykiem informatyki, ale myślę, że ten problem ze światem rzeczywistym należy tutaj. Problem Moja firma ma kilka jednostek w całym kraju. Zaoferowaliśmy pracownikom możliwość pracy na innej jednostce. Ale jest warunek: łączna liczba pracowników w jednostce nie może się zmienić. Oznacza to: Pozwolimy pracownikowi opuścić jego jednostkę, jeśli …
4
Liczenie słów przyjętych przez zwykłą gramatykę
W przypadku zwykłego języka (NFA, DFA, gramatyki lub wyrażenia regularnego), jak można policzyć liczbę słów akceptowanych w danym języku? Interesujące są zarówno „z dokładnie n literami”, jak i „z najwyżej n literami”. Margareta Ackerman ma dwa artykuły na powiązany temat wyliczania słów zaakceptowanych przez NFA, ale nie byłem w stanie …
4
Brakuje artykułów z Wikipedii
O których brakujących tematach TCS na Wikipedii najbardziej chciałbyś znaleźć artykuł? Mogą to być rażące pominięcia lub po prostu tematy, które Twoim zdaniem powinny zawierać artykuł. Poproszę jeden temat na odpowiedź, aby głosować na najbardziej poszukiwanych. Aktualizacja 5/2/2017 : Shuchi Chawla stara się poprawić zasięg TCS na Wikipedii . Dodam …
2
Maksymalne / maksymalne niezależne zestawy
Czy jest coś znanego o klasie grafów z właściwością, że wszystkie maksymalne niezależne zbiory mają tę samą liczność, a zatem są maksymalnymi IS? Na przykład weź zestaw punktów na płaszczyźnie i rozważ wykres przecięcia między wszystkimi segmentami między parami punktów w zestawie. (segmenty-> wierzchołki, przecięcia-> krawędzie). Ten wykres będzie miał …
5
Długotrwałe błędy w informatyce
To jest moje pierwsze pytanie na stosie cstheory, więc nie bądź zbyt niegrzeczny, jeśli w jakiś sposób naruszam etykietę) Jak wiemy, w matematyce nawet znani matematycy, supergwiazdy i geniusze od czasu do czasu popełniają poważne błędy. Na przykład, zarówno twierdzenie 4-kolorowe, jak i twierdzenie Fermata dostarczają nam dramatycznych przypadków, w …
5
Jaka jest różnica między dowodami a programami (lub między propozycjami i typami)?
To pytanie zostało przeniesione z przepełnienia stosu, ponieważ można na nie odpowiedzieć na teoretycznej wymianie stosu komputerów. Migrował 8 lat temu . Biorąc pod uwagę, że Korespondencja Curry-Howarda jest tak szeroko rozpowszechniona / rozszerzona, czy istnieje jakaś różnica między dowodami a programami (lub między propozycjami i typami)? Czy naprawdę możemy …
2
Jaka jest złożoność odróżnienia prawdziwego widma Fouriera od fałszywego?
PHPHPH urządzenie ma dostęp oracle losowej logicznej funkcji f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} , a dwa Fouriera widma ggg i hhh . Widma Fouriera funkcji fff są zdefiniowane jako F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R : F(s)=∑x∈{0,1}n(−1)(s⋅xmod 2)f(x)F(s)=∑x∈{0,1}n(−1)(s⋅xmod 2)f(x)F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x) Jedno z ggg lub hhh to prawdziwe …
4
Kompendium najlepszych wyników aproksymacji i twardości dla problemów optymalizacji NP
Czy znasz jakieś aktualne wiki poświęcone problemom z optymalizacją NP z najlepszym wynikiem przybliżenia i twardości? Na podstawie informacji zwrotnych wydaje się, że można bezpiecznie założyć, że nie ma takiego zasobu (zobacz dwie odpowiedzi na końcu tego pytania). - dodano 8 lutego. Ponieważ w ciągu ostatnich dwóch dziesięcioleci pojawiło się …
3
Obliczanie wszelkich informacji o Max-3SAT
O wzorze 3CNF pozwolić jest w maksymalna liczba zadowoleni klauzul jakimkolwiek wyznaczeniem . Wiadomo, że wartość Max-3SAT jest trudna do przybliżenia (z zastrzeżeniem P ≠ NP), tj. Nie ma algorytmu czasu policyjnego, którego dane wejściowe to formuła 3CNF , a których wynikiem jest liczba taka, że mieści się w zakresie …
4
Czy istnieje niepełny model Turinga, którego problem zatrzymania jest nierozstrzygalny?
Nie mogę wymyślić żadnego takiego modelu, może jakiejś formy wypisanego rachunku lambda? jakiś elementarny automat komórkowy? To prawie obaliłoby „zasadę równoważności obliczeniowej” Wolframa: Prawie wszystkie procesy, które nie są oczywiście proste, można postrzegać jako obliczenia o podobnym stopniu zaawansowania
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.