Teoretyczne informatyka

34
Algorytmy aproksymacyjne dla problemów w P.

Zwykle myśli się o zbliżeniu rozwiązań (z gwarancjami) do problemów trudnych dla NP. Czy trwają badania nad zbliżeniem problemów, o których wiadomo, że są w P? To może być dobry pomysł z kilku powodów. Z góry mojej głowy algorytm aproksymacyjny może działać ze znacznie mniejszą złożonością (lub...

34
Twardość przeskakuje w złożoności obliczeniowej?

Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami. -caterpillar jest drzewem, utworzony z głównego toru hodując ścieżki krawędziach rozłączny o długości co...

33
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...

33
„Klasa Steve'a”: pochodzenie SC

„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...

33
Najtrudniejszy znany problem naturalny w P?

Zastanawiam się, jaka jest (obecnie) największa liczba , tak że znany jest naturalny problem z następującymi właściwościami:kkk algorytm został już, że do tego problemu.O(nk)O(nk)O(n^k) Dla każdego ustalonego algorytmu no znany jest ten sam problem. (Zauważ, że istnieć szybszy algorytm , tylko...

33
Klasy typów a interfejsy obiektowe

Nie sądzę, że rozumiem klasy typów. Czytałem gdzieś, że myślenie o klasach typów jako „interfejsach” (od OO), które implementuje typ, jest błędne i wprowadza w błąd. Problem polega na tym, że mam problem z postrzeganiem ich jako czegoś innego i jak to jest złe. Na przykład, jeśli mam klasę typu (w...

33
Jaka jest objętość informacji?

To pytanie zostało zadane Jeannette Wing po prezentacji PCAST na temat informatyki. „Czy z punktu widzenia fizyki istnieje maksymalna ilość informacji, którą możemy mieć?” (Fajne wyzwanie dla teoretycznej społeczności informatycznej, ponieważ myślę, że rodzi to pytanie „Czym jest informacja?”)...

33
Odniesienie do twardości NP 3-zabarwienia?

Mam pytanie historyczne. Próbuję ustalić odniesienie dla faktu, że 3-kolorowalność grafów (alternatywnie, kolorowalność dla danego k ≥ 3 ) jest NP-trudna.kkkk ≥ 3k≥3k\geq 3 Kuszącą odpowiedzią jest „oryginał Karpa”, ale to nieprawda. Oto skan: Reducibility Among Combinatorial Problems, Karp...