czemu to nie ma znaczenia?
Bo każdego SATa (no, poza 2SAT ;)) da się zredukować do 3SATa.
To prawda, jednak formuła po zapisaniu w 3CNFie może się wykładniczo wydłużyć, a to już budzi uzasadnione obawy.
To prawda, jednak formuła po zapisaniu w 3CNFie może się wykładniczo wydłużyć, a to już budzi uzasadnione obawy
Dla każdej formuły \phi istnieje odpowiadająca jej formuła \phi_{3cnf} \in 3CNF. Pytając o spełnialność \phi, de facto pytamy melmażelona czy \phi_{3cnf} \in 3SAT. Nie obchodzi nas długość \phi_{3cnf} - jest to dobra, poprawna instancja problemu 3SAT i melmażelon będzie również ją umiał przetrawić. Także nie miałbym tych obaw.
Gdzie odbywają się ćwiczenia 27 maja?
4 polubienia
Kolejne listy idą tak:
A jak idzie lista na 10 czerwca?
Otóż idzie ona następująco:
167 – 169 i 185–191
- [167] Czy c należy do instancji problemu? (pewnie nie)
- [168] Jak zachowuje się algorytm z zadania dla G takiego, że \sigma(G) \gt 1? (pewnie w wielomianowym czasie mówi “NIE”)
- [169] Czy c jest naturalne? (pewnie tak i pewnie nie ma to znaczenia)
(takie wieczorne przemyślenia z @w105)
[167] c nie należy do instancji . Dlatego najpierw w zadaniu ustalono c a potem zdefiniowano problem;
[168] w zadaniu, jak widać, niczego się nie zakłada o tym jak się ten algorytm zachowuje dla innych wejść; skoro się niczego nie zakłada to znaczy że się nie zakłada z nie że się domniemuje jakeiś założenie;
[169] to nie ma znaczenia; gdyby istniało takie rzeczywiste c to istniałoby też naturalne; nawet nieskończenie wiele naturalnych by istniało.
Czy w zadaniu 189 powinno być (i>=2) zamiast (p >=2)? Czy w ostatniej linijce powinno być, że Olek wartościuje q_{i-1}?
Obawiam się że ma Pani rację. Dwa razy. Zaraz poprawię, tak żeby w przyszłym roku nie mieć tych błędów już.
Do treści zadania 186 także wkradł się mały chochlik drukarski, który błędnie odnosi czytelników do zadania 184 (zamiast 185).
Myślę że to nie chochlik. To mnie trzeba już zastrzelic.
2 polubienia
A na ostatnią w tym semestrze listę jakie będą zadania do zrobienia?
1 polubienie
No jak to jakie ? 195 oraz 197 – 201. Zadanie 195 lepiej robić po poniedziałkowym wykładzie.
Wydaje mi się, że zadanie 195 zostało rozwiązane na wykładzie. Czy wystarczy to rozwiązanie słowo w słowo powtórzyć na ćwiczeniach, czy może powinniśmy wymyślić coś oryginalnego?
4 polubienia