Ικανοποιησιμότητα

Δίνεται η παρακάτω παραλλαγή του προβλήματος της Ικανοποιησιμότητας (SAT):

HSAT: Δοθείσης μιας Λογικής έκφρασης Φ σε Κανονική Συζευκτική Μορφή, ορισμένη σε n μεταβλητές, υπάρχει ανάθεση τιμών που να ικανοποιεί την Φ και η οποία να αποδίδει τιμή αλήθεια (true) σε ακριβώς n/2 μεταβλητές της Φ;

A) Αποδείξτε ότι το πρόβλημα HSAT ανήκει στην κλάση NP.

B) Αποδείξτε ότι το HSAT είναι ΝΡ-δύσκολο με αναγωγή από το SAT.

Γ) Υποθέτοντας ότι το πρόβλημα HSAT ανήκει στην κλάση Ρ, σχεδιάστε πολυωνυμικό αλγόριθμο για το πρόβλημα SAT.

Δ) Υποθέτοντας ότι το πρόβλημα SAT ανήκει στην κλάση P, υπάρχει πολυωνυμικός αλγόριθμος για το πρόβλημα HSAT ή όχι και γιατί;