Często, gdy bierzemy udział w konferencjach TCS, zauważamy kilka drobiazgów, którymi chcielibyśmy się zająć organizatorzy konferencji. A kiedy organizujemy konferencje, już o tym zapomnieliśmy. Stąd pytanie: jakie małe kroki moglibyśmy łatwo podjąć, aby usprawnić konferencje TCS ? Mam nadzieję,...
Chciałbym napisać ankietę na temat zastosowań topologii w informatyce. Planuję opisać historię pomysłów topologicznych w dziedzinie informatyki, a także zwrócić uwagę na kilka aktualnych osiągnięć. Byłoby niezwykle pomocne, gdyby ktokolwiek mógł udzielić informacji na temat któregokolwiek z...
Szukam przykładów problemów sparametryzowanych liczbą , gdzie twardość problemu nie jest monotoniczna w k . Z mojego doświadczenia wynika, że większość problemów ma przejście jednofazowe, na przykład k- SAT ma przejście jednofazowe od k ∈ { 1 , 2 } (gdzie problem występuje w P) do k ≥ 3 (gdzie...
W TCS często używamy potężnych wyników i pomysłów z matematyki klasycznej (algebry, topologii, analizy, geometrii itp.). Jakie są przykłady sytuacji, w której sytuacja się odwróciła? Oto niektóre, o których wiem (a także, aby dać smak wyników, o które pytam): Sześcienne pianki (Guy...
tło Kilka lat temu, kiedy byłem studentem, otrzymaliśmy zadanie domowe z analizy zamortyzowanej. Nie udało mi się rozwiązać jednego z problemów. Poprosiłem o to w teorii porównawczej , ale nie uzyskałem zadowalającego rezultatu. Pamiętam kurs, który TA nalegał na coś, czego nie mógł udowodnić, i...
Powszechnie przypuszcza się, że , optymalny wykładnik mnożenia macierzy, w rzeczywistości jest równy 2. Moje pytanie jest proste:ωω\omega Jakie mamy powody, by sądzić, że ?ω=2ω=2\omega = 2 Mam świadomość szybkich algorytmów, takich jak Coppersmith-Winograd, ale nie wiem, dlaczego można je...
Czy znasz rozsądne algorytmy działające w czasie wielomianowym w (Długość wejściowa + Długość wyjściowa), ale których asymptotyczny czas działania w tej samej mierze ma naprawdę ogromny wykładnik / stałą (przynajmniej tam, gdzie jest udowodniona górna granica czasu działania taka...
Po przestudiowaniu deterministycznych automatów skończonych (DFA) w undergrad poczułem, że są one bardzo dobrze rozumiane. Moje pytanie brzmi, czy jest coś, czego wciąż nie rozumiemy. Nie mam na myśli uogólnień DFA, ale oryginalne niezmodyfikowane DFA, które badamy w studiach licencjackich. To...
Jestem nowy na stronie. Na mathoverflow byłoby to wiki społeczności, ale nie widzę, jak to tutaj ustawić. Nie pytanie badawcze, ale miejmy nadzieję, że zainteresuje profesjonalnych teoretycznych informatyków. Teoretycznie jestem studentem drugiego roku i zastanawiałem się, jaką radę ma społeczność...
Przez lata przyzwyczaiłem się do tego, że wiele twierdzeń TCS zostało udowodnionych przy użyciu dyskretnej analizy Fouriera. Transformacja Walsha-Fouriera (Hadamarda) jest przydatna w praktycznie każdym podpolu TCS, w tym w testowaniu właściwości, pseudolosowości, złożoności komunikacji i...
Zastanawiam się nad tym pytaniem. Kiedy ludzie opisują problem P vs. NP, często porównują NP klasy do kreatywności. Zauważają, że skomponowanie symfonii jakości Mozarta (analogicznej do zadania NP) wydaje się znacznie trudniejsze niż sprawdzenie, czy już skomponowana symfonia ma jakość Mozarta...
Jakie są ogólne wytyczne dotyczące sprawdzania twoich dowodów? Uważam, że jest to ważne dla absolwentów takich jak ja. Wiem już, co musimy zrobić, aby coś udowodnić, ale zawsze musisz wszystko sprawdzić przed wysłaniem. Nawet do twojego własnego doradcy. Opracowałem sobie strategie metodą prób i...
W wątku Główne nierozwiązane problemy w informatyce teoretycznej? Iddo Tzameret napisał następujący doskonały komentarz: Myślę, że powinniśmy rozróżnić między głównymi otwartymi problemami, które są postrzegane jako podstawowe problemy, takie jak P≠NPP≠NP P\neq NP , i głównymi otwartymi...
Wraz z pojawieniem się Internetu (i zdrowego rozsądku) rośnie zapotrzebowanie na badania o otwartym dostępie. Kilku badaczy (w tym ja) uważa za frustrujące, że opublikowane artykuły naukowe recenzowane są za ścianami płatnymi. Szukam czasopism i konferencji (związanych z informatyką teoretyczną,...
Gdy projektuję algorytm dla nowego problemu, jeśli po pewnym czasie nie mogę znaleźć algorytmu wielomianowego czasu, mogę spróbować udowodnić, że jest to trudny NP. Jeśli mi się uda, wyjaśniłem, dlaczego nie mogłem znaleźć algorytmu czasu wielomianowego. Nie chodzi o to, że wiem na pewno, że P! =...
Algorytmy genetyczne nie cieszą się dużą popularnością w świecie teorii, ale są one dość dobrze stosowaną metodą metaheurystyczną (przez metaheurystyczny mam na myśli technikę, która ogólnie stosuje się w wielu problemach, takich jak wyżarzanie, opadanie gradientu i tym podobne). W rzeczywistości...
Niedawno, rozmawiając z fizykiem, twierdziłem, że z mojego doświadczenia, kiedy problem, który naiwnie wydaje się, że powinien on zająć wykładniczy czas, okazuje się niekoniecznie w P lub BPP, „nadrzędny powód”, dla którego redukcja może być zazwyczaj zidentyfikowany --- i prawie zawsze powód ten...
Natknąłem się na algorytm wielomianowy, który rozwiązuje 2SAT. Uważam za zaskakujące, że 2SAT znajduje się w P, gdzie wszystkie (lub wiele innych) instancji SAT są NP-Complete. Co wyróżnia ten problem? Co sprawia, że jest to takie proste (NL-Complete - nawet łatwiejsze niż...
Jakich narzędzi używasz do pisania prac? Z mojego małego doświadczenia teoretycy spędzają dużo czasu na pisaniu i doskonaleniu artykułów, poza tym, że są kreatywni. Oznacza to, że przekazują swoją pracę innym ludziom. Być może artykuły nie są odpowiednim sposobem, ale należy to pozostawić do...
Celem tego pytania jest zebranie przykładów z teoretycznej informatyki, w której pomocne było systematyczne korzystanie z komputerów budując przypuszczenie, które prowadzi do twierdzenia, fałszowanie przypuszczeń lub podejścia dowodowego, konstruowanie / weryfikacja (części) dowodu. Jeśli masz...