Często słyszymy o klasycznych badaniach i publikacjach z zakresu złożoności obliczeniowej (Turing, Cook, Karp, Hartmanis, Razborov itp.). Zastanawiałem się, czy są ostatnio opublikowane artykuły uważane za przełomowe i konieczne do przeczytania. Mam na myśli ostatnie 5/10...
Mark Dominus zebrał kilka przykładów redukcji czasu wielomianowego od różnych trudnych problemów NP do dopasowania „wyrażenia regularnego” . Wyobrażanie sobie weryfikacji w czasie wielomianowym nie jest ogromnym skokiem. Jak zilustrujesz klasę NP-zupełną studentom lub przyjaciołom z innych...
Chociaż zdałem kilka kursów z teorii prawdopodobieństwa, zarówno w szkole średniej, jak i na uniwersytecie, trudno mi czytać artykuły TCS, jeśli chodzi o prawdopodobieństwo. Wydaje się, że autorzy artykułów TCS są bardzo dobrze zaznajomieni z prawdopodobieństwem. Magicznie działają ze wzorami...
W artykule Losowa hipoteza Oracle jest fałszywa , autorzy (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan i Rohatgi) omawiają implikacje hipotezy losowo-wyroczni . Twierdzą, że niewiele wiemy o separacjach między klasami złożoności, a większość wyników wymaga albo przyjęcia rozsądnych założeń,...
To pytanie dotyczy problemów, dla których istnieje duża otwarta luka złożoności między znaną dolną i górną granicą, ale nie z powodu otwartych problemów dotyczących samych klas złożoności. Mówiąc ściślej, powiedzmy, że problem ma klasy przerw (z A ⊆ B , nie jednoznacznie zdefiniowane), jeśli A...
Wokół jest mnóstwo problemów z kompletnym NP i źródła je zbierające, np. Patrz książka Garey i Johnsona. Byłbym również zainteresowany, aby zobaczyć listę problemów uzupełniających NEXP. Czy jest dostępny? Ponieważ zakładam, że nie ma, otwieram to pytanie (czy to ma być wiki społeczności? Nie wiem...
Pewne paradoksy matematyczne i logiczne można prawdopodobnie automatycznie zastosować do komputerów, ale czy istnieją jakieś paradoksy odkryte w samej informatyce? Przez paradoksy rozumiem sprzeczne z intuicją wyniki, które wyglądają jak
Richard J. Lipton został wybrany zwycięzcą nagrody Knuth Prize 2014 „za wprowadzenie nowych pomysłów i technik”. Jakie są według Ciebie główne nowe pomysły i techniki opracowane przez Lipton? Uwaga. To pytanie stanie się wiki społeczności, proszę podać jeden taki pomysł, technikę lub wynik na...
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...
Jedną z miłych rzeczy w ewolucji we wszechświecie o trzech wymiarach przestrzennych jest to, że rozwinęliśmy umiejętności rozwiązywania problemów dotyczące obiektów w przestrzeni. Tak więc na przykład możemy myśleć o tryplecie liczb jako o punkcie 3-d, a zatem obliczenia o tripletach liczb jako o...
Interesują mnie przykłady problemów, w których twierdzenie, które pozornie nie ma nic wspólnego z mechaniką / informacją kwantową (np. Mówi coś o obiektach czysto klasycznych), może jednak zostać udowodnione za pomocą narzędzi kwantowych. Badanie Kwantowe dowody dla klasycznych twierdzeń (A....
Jestem informatykiem biorącym udział w kursie na temat topologii (posypka topologii punktowej mocno przyprawionej teorią kontinuum). Zainteresowały mnie problemy decyzyjne testujące opis przestrzeni (uproszczeniem) dla właściwości topologicznych; zachowane do homeomorfizmu. Wiadomo na przykład, że...
Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy...
W solverach SAT często można znaleźć metody płaszczyzny cięcia, zmienną propagację, odgałęzienie i wiązanie, uczenie się klauzul, inteligentne cofanie, a nawet ręcznie tkaną ludzką heurystykę. Jednak przez dziesięciolecia najlepsze solwery SAT polegały w dużej mierze na technikach sprawdzania...
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...
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...
Oczywiście niektóre wyniki złożoności mogą się zawalić w przypadku języków jednoargumentowych, ale zastanawiam się, czy istnieje gdzieś ankieta podsumowująca znane wyniki w tym przypadku: rodzaj zoo złożoności dla języków jednoargumentowych. Czy znasz takie
Będę uczestniczył w mojej pierwszej konferencji informatycznej i po przeczytaniu porady, jak ulepszyć konferencje , zauważyłem, że kilka sugestii dotyczyło studentów na pierwszej konferencji. Jakie masz rady dla ucznia uczestniczącego w jego pierwszej konferencji i na czym powinien się...
Istnieje reputacja, że w informatyce nie mamy książek popularnonaukowych. Oczywiście to nie do końca prawda! (W tym samym duchu listy Co Książki każdy powinien przeczytać? , Jakie dokumenty powinien każdy przeczytać? , Co każdy powinien oglądać filmy? A zainspirowana Ulubiony popularnej książce...
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...