Teoretyczne informatyka big-list

5

Obecnie próbuję znaleźć problemy pełne EXPSPACE (głównie w celu znalezienia inspiracji do redukcji) i jestem zaskoczony małą liczbą nadchodzących wyników. Jak dotąd je znalazłem i mam problem z rozwinięciem listy: uniwersalność (lub inne właściwości) wyrażeń regularnych z potęgowaniem. problemy związane z systemami dodawania wektorów nieobserwowalne gry (patrz na przykład ten …

23 cc.complexity-theory reference-request big-list

4

Główne nierozwiązane problemy w systemach rozproszonych?

Zainspirowany tym pytaniem , jakie są główne problemy i istniejące rozwiązania, które wymagają ulepszenia w (teoretycznej) dziedzinie systemów rozproszonych. Coś jak protokoły członkostwa, spójność danych?

23 big-list dc.distributed-comp

1

Główne błędy w zaakceptowanych dokumentach FOCS / STOC [zamknięte]

W obecnej formie to pytanie nie pasuje do naszego formatu pytań i odpowiedzi. Oczekujemy, że odpowiedzi poparte będą faktami, referencjami lub wiedzą fachową, ale to pytanie prawdopodobnie będzie wymagało debaty, argumentów, ankiet lub rozszerzonej dyskusji. Jeśli uważasz, że to pytanie można poprawić i ewentualnie ponownie otworzyć, odwiedź centrum pomocy w …

23 soft-question big-list paper-review

8

wykresy z rzeczywistych problemów

Gdzie mogę znaleźć wykresy dotyczące rzeczywistych problemów? Dwa znane mi repozytoria: Kolekcja rzadkich matryc University of Florida Bodlaender's TreewidthLib

23 graph-theory big-list co.combinatorics data-sets

9

Redukcje z książki.

Jest to zgodne z „ Algorytmami z książki ”. Chociaż redukcje są również algorytmami, pomyślałem, że wątpliwe jest, aby pomyśleć o redukcji w odpowiedzi na pytanie o algorytmy z książki. Stąd osobne zapytanie! Wszelkie redukcje są mile widziane. Zacznę od bardzo prostej redukcji od osłony wierzchołków do multikutów na gwiazdach. …

22 ds.algorithms np-hardness big-list reductions

2

Języki, których nie możemy (nie) okazują się wolne od kontekstu

Szukam języków, które „prawdopodobnie nie są wolne od kontekstu”, ale nie jesteśmy w stanie (nie) udowodnić tego przy użyciu znanych standardowych technik. Czy jest ostatnia ankieta na ten temat lub otwarta sekcja problemowa z ostatniej konferencji? Prawdopodobnie nie ma wielu języków, o których nie wiadomo, że są CF, więc jeśli …

21 reference-request big-list context-free

7

Złoty współczynnik lub Pi w czasie wykonywania

Istnieje wiele miejsc, w których pojawiają się liczby i . Ciekawi mnie algorytmy, których czas działania zawiera złoty współczynnik lub w wykładniku.ππ\pi(1+5–√)/2(1+5)/2(1+\sqrt5)/2ππ\pi

21 reference-request big-list

3

Problemy, które są NP-zupełne w przypadku randomizacji lub redukcji P / poli.

W tym pytaniu wydaje się, że zidentyfikowaliśmy naturalny problem, który jest zupełny NP przy redukcjach losowych, ale być może nie przy redukcjach deterministycznych (chociaż zależy to od tego, które niesprawdzone założenia teorii liczb są prawdziwe). Czy znane są inne problemy? Czy istnieją jakieś naturalne problemy, które są NP-zupełne w przypadku …

20 cc.complexity-theory np-hardness big-list randomness reductions

6

Narzędzia do wizualizacji analizy sieci / sieci społecznościowych?

Używałem Junga ( http://jung.sourceforge.net/ ) do wizualizacji rangi strony i stwierdziłem, że jest trochę powolna i trudna do skalowania poza 100 węzłów. Zastanawiałem się, jakich innych narzędzi używają ludzie do analizy i wizualizacji sieci / sieci społecznościowych.

20 graph-theory big-list cg.comp-geom software graph-drawing

22

Jakie algorytmy są najczęściej stosowane w praktyce?

Zablokowana . To pytanie i odpowiedzi są zablokowane, ponieważ pytanie jest nie na temat, ale ma znaczenie historyczne. Obecnie nie akceptuje nowych odpowiedzi ani interakcji. Które algorytmy są najczęściej używane? Napisz jeden algorytm na odpowiedź, staraj się, aby twoja odpowiedź była krótka (jedna lub dwie linie).

19 ds.algorithms big-list

2

Długotrwałe przypuszczenia później potajemnie udowodniono przez domniemanie

Chciałbym wiedzieć, czy w TCS istniały przypuszczenia, które od dawna nie zostały udowodnione, a które później udowodniono na podstawie innego twierdzenia, które mogłyby być łatwiejsze do udowodnienia.

18 reference-request soft-question big-list

11

Czy występują problemy, których najbardziej znany algorytm ma czas działania

Nigdy wcześniej nie widziałem algorytmu z logiem w mianowniku i zastanawiam się, czy w tym formularzu są jakieś przydatne algorytmy? Rozumiem wiele rzeczy, które mogą powodować mnożenie współczynnika logu w czasie wykonywania, np. Algorytmy sortowania lub oparte na drzewach, ale co może powodować dzielenie przez współczynnik log?

18 ds.algorithms big-list time-complexity

4

Lista twierdzeń stwierdzających, że P nie jest równe NP wtedy i tylko wtedy, gdy

Myślę, że dobrym pomysłem byłoby sporządzenie listy twierdzeń stwierdzających, że P nie jest równe NP wtedy i tylko wtedy, gdy takie i takie wyjścia, pewna klasa złożoności jest zawarta w innej klasie złożoności i tak dalej.

18 cc.complexity-theory big-list p-vs-np

7

Uniwersytety dla informatyki kwantowej / informacje?

Które uniwersytety mają silny program obliczeń kwantowych i oferują pewien rodzaj obliczeń kwantowych / kursów informacyjnych / badań? Ma to na celu zebranie przydatnej listy dla osób rozważających studia podyplomowe w tych dziedzinach, a nie dyskutowanie o tym, co jest „najlepsze”. Aby ta lista była przydatna, proszę podać krótki opis …

18 soft-question quantum-computing big-list quantum-information

1

Lista (nierozwiązanych) problemów złożoności wynikających z PL

Jakie są niektóre główne, otwarte problemy ze złożonością obliczeniową, które wynikają z języków programowania, zwłaszcza z analizy i kompilacji programów? Szukam problemów na linii „złożoności czasowej wnioskowania typu Hindleya-Milnera” lub „złożoności czasowej 0CFA” (chociaż obie są rozwiązanymi problemami).

17 cc.complexity-theory pl.programming-languages big-list open-problem

Pytania otagowane jako big-list