Pytania otagowane jako examples

11
Powszechne fałszywe przekonania w informatyce teoretycznej
EDYCJA PRZY 10/12/08: Spróbuję zmodyfikować pytanie, aby zainteresować większą liczbą osób dzieleniem się opiniami. POTRZEBUJEMY twoich datków! Ten post jest inspirowany jednym z MO: Przykłady powszechnych fałszywych przekonań w matematyce . Wielkie listy czasami generują ogromną liczbę odpowiedzi, których jakości trudno jest kontrolować, ale po sukcesie powiązanego postu na MO …
14
Gdzie i jak komputery pomogły udowodnić twierdzenie?
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 konkretny przykład, opisz, jak to zrobiono. Być może pomoże to innym w bardziej efektywnym korzystaniu …
2
Łatwy w optymalizacji, ale trudny do oceny
Czy są znane naturalne przykłady problemów z optymalizacją, dla których znacznie łatwiej jest stworzyć optymalne rozwiązanie niż ocenić jakość danego rozwiązania kandydującego? Ze względu na konkretność możemy rozważyć rozwiązania problemów optymalizacji w postaci wielomianowej w postaci: „biorąc x, zminimalizuj ”, gdzie f : { 0 , 1 } ∗ × …
1
Hipoteza Hartmanisa-Stearnsa i obliczalne liczby transcendentalne
W artykule z 1965 r. „ O złożoności algorytmów ” autorstwa Hartmanisa i Stearnsa autorzy przypuszczają, że jeśli maszyna Turinga w czasie rzeczywistym oblicza liczbę rzeczywistą na przykład w podstawie 10, to r jest albo liczbą wymierną, albo liczbą liczba transcendentalna.rrrrrr Czy istnieje obliczalna liczba transcendentalna, która nie jest obliczalna …
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.