Pytania otagowane jako proofs

Używane w przypadku pytań dotyczących istniejących lub możliwych dowodów konkretnego twierdzenia lub przypuszczenia

1
Przykłady algorytmów i dowodów, które wydają się poprawne, ale nie są
W moim wstępie do kursu programowania dowiadujemy się o metodzie inicjalizacji, konserwacji i terminacji, aby udowodnić, że algorytm działa zgodnie z oczekiwaniami. Musieliśmy jednak tylko udowodnić, że algorytm, o którym wiadomo, że jest poprawny, jest poprawny. Nigdy nie byliśmy proszeni o wykazanie, że algorytm jest nieprawidłowy. Czy są jakieś klasyczne …
1
W jaki sposób udowodniono, że MA wersji SETH jest fałszywa?
Zgodnie z tym artykułem , który omawia niedeterministyczne rozszerzenie hipotezy silnego czasu wykładniczego (SETH), „[…] Williams ostatnio wykazał, że podobne hipotezy dotyczące złożoności k-TAUT Merlina i Artura są fałszywe”. Jednak ten artykuł przytacza jedynie osobistą korespondencję. W jaki sposób udowodniono, że MA wersji SETH jest fałszywa? Podejrzewam, że wiąże się …
1
Dowody poprawności klasycznych Paxos i Fast Paxos
Czytam artykuł „Fast Paxos” autorstwa Leslie Lamport i utknąłem z dowodami poprawności zarówno klasycznych Paxos, jak i Fast Paxos. Aby zachować spójność, wartość wybrana przez koordynatora w fazie 2 a w rundzie i powinna spełniaćvvv2 a2a2ajaii Dla dowolnej rundy j < i żadna wartość inna niż v nie była lub …
2
Prosty dowód na najgorszy przypadek Ω (n lg n) wyjątkowości / odrębności?
Istnieje kilka dowodów na dolną granicę logiczną dla problemu wyjątkowości / odrębności elementu (opartej na drzewach obliczeń algebraicznych lub argumentach przeciwnych), ale szukam takiego, który byłby wystarczająco prosty do zastosowania w pierwszym kursie analizy i projektowania algorytmów. Taki sam „poziom trudności” jak dolna granica sortowania byłby w porządku. Również każde …
1
Dlaczego Feige-Fiat-Shamir nie jest zerową wiedzą bez znaków?
W rozdziale 10 HAC (10.4.2) widzimy dobrze znany protokół identyfikacyjny Feige-Fiat-Shamir oparty na dowodzie zerowej wiedzy przy użyciu (przypuszczalnej) trudności w wyodrębnieniu modulo pierwiastków kwadratowych z kompozytu, który jest trudny do uwzględnienia. Podam schemat własnymi słowami (i mam nadzieję, że dobrze to zrobię). Zacznijmy od prostszego schematu: niech nnn będzie …
2
Interaktywny dowód liczby Boga?
Ostatnio uczyłem się o interaktywnych dowodach i zastanawiałem się, czy cała ta sprawa była jedynie ciekawostką teoretyczną, czy też miała jakieś praktyczne zastosowania. Myślałem, że zacznę od przykładu, który przyszedł mi do głowy pod prysznicem: Ostatnio ogłaszano, że „liczba Boga” = 20. (Liczba Boga to minimalna liczba kroków potrzebnych do …
2
O wiarygodności P w porównaniu z NP
Po pierwsze, moje rozumienie twierdzenia o niekompletności Gödla (i logiki formalnej w ogóle) jest bardzo naiwne, podobnie jak moja wiedza z zakresu teoretycznej informatyki (co oznacza, że ​​tylko jeden kurs magisterski odbył się, gdy jestem jeszcze studentem), więc pytanie może być bardzo naiwny. O ile mogłem znaleźć, wiarygodność P w …
3
Dowody znalezione przez komputer
W 1996 r. Długotrwały otwarty problem został rozwiązany przez komputer; mianowicie, że algebra Robbinsa i algebra Boole'a są takie same. Dowód został znaleziony przez automatyczną powiedzonkę twierdzeń. Ponadto znany dowód twierdzenia o czterech kolorach zawiera generowane komputerowo komponenty. Celem tego pytania jest wykazanie dowodów, które zostały (całkowicie lub częściowo) znalezione …
3
Gdzie mogę uzyskać pomoc w zakresie badań / publikacji?
Od jakiegoś czasu opracowuję algorytm SAT i doszedłem do punktu, w którym chciałbym się nim podzielić. Nie znam wielu ludzi informatyki i nie jestem pewien, dokąd się zwrócić. Zastanawiam się, jakie zasoby są dostępne dla kogoś z algorytmem, który rozważa publikację. Potrzebuję również pomocy w analizie czasu działania i poprawności …
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.