Kilka pytań dotyczących przedmiotu AiSD

Witam, niedługo będę pisał poprawkę z przedmiotu AiSD i mam kilka powiązanych zadań, na które nie umiem udzielić odpowiedzi (bądź nie jestem pewny ich poprawności), dużo szperałem w internecie, ale nie mogłem znaleźć odpowiedzi, bądź niejednoznacznej. Proszę Was o pomoc, jeśli ktoś umie udzielić odpowiedzi na jakieś pytanie, bądź zweryfikować poprawność odpowiedzi, z góry dziękuję. Oto pytania:

1. Czy istnieje optymalizacyjny odpowiednik problemu spełnialności? Odpowiedź uzasadnić.
2. Wykazać przynależność do klasy P problemu sprawdzania podzielności liczby przez 4.
3. Dlaczego badając trudność problemów kombinatorycznych możemy ograniczyć się jedynie do problemów decyzyjnych?
4. Napisać program dla maszyny RAM obliczający wartość 22^n o złożoności O(n) dla jednorodnego kryterium kosztów. Jaka byłaby złożoność tego algorytmu dla kosztu logarytmicznego?

A tu zadania, na które nie wiem czy udzieliłem poprawnej/pełnej odp:

5. Dlaczego badając trudność problemów kombinatorycznych możemy ograniczyć się jedynie do problemów decyzyjnych?
   Ponieważ rozwiązując problem decyzyjny dostajemy odpowiedź czy konkretny problem kombinatoryczny może zostać rozwiązany.
6. Zdefiniować i opisać różnice zachodzące między NP-zupełnością a silną NP-zupełnością. Jak wykazujemy przynależność do obu tych klas problemów decyzyjnych?
   RÓŻNICE:
   Problemy silnie NP-zupełne pozostają takimi nawet jeśli ograniczyć im dane wejściowe jakimś wielomianem i nie mogą zostać rozwiązane w czasie wielomianowym, natomiast gdy dane wejściowe problemów NP.-zupełnych są ograniczone jakimś wielomianem to mogą być rozwiązne w czasie wielomianowym
   Wykazywanie
   a)SILNEJ: Problem decyzyjny jest silnie NP-zupełny, jeśli należy do NP i istnieje wielomian p określony dla liczb całkowitych, dla którego Pip jest NP-zupełny (problemami silnie NP-zupełnymi są problemy NP-zupełne nieliczbowe - inaczej: problem NP-zupełny nieliczbowy jest silny).
   b)ZWYKŁEJ: Problem jest NP-zupełny jeśli należy do klasy problemów NP i jest NP-trudny. Dla wykazania NP-zupełności badanego problemu decyzyjnego wystarczy przetransformować do niego wielomianowo dowolny znany problem NP-zupełny.
7. Co to jest funkcja złożoności obliczeniowej?
   Mówimy że problem ma złożoność O(g(n)) rzędu g(n) jeżeli algorytm go rozwiązujący dla n danych wejściowych potrzebuje co najwyżej cg(n) czasu dla uzyskania wyniku, gdzie c jest pewną stałą rzeczywistą.

1. No możesz na przykład szukać najmniejszej ilości wartościowań zmiennych logicznych jako "prawda" które będzie spełniać formułę.
2. Wystarczy że pokażesz wielomianowy algorytm który ten problem rozwiązuje.

Odnośnie drugiego (podzielności przez 4) - wpadłem właśnie na to, że wystarczy badać dwa ostatnie bity takiej liczby - jeśli są 00 to liczba jest podzielna przez 4.
Pewnie to jakoś ładnie się nazywa i jest w literaturze jako proste zadanko, ale nigdy wcześniej nad tym nie myślałem :D