Kλάση NP

Η κλάση coNP είναι η κλάση των συμπληρωματικών των προβλημάτων της κλάσης NP. Με άλλα λόγια, είναι η κλάση των προβλημάτων για τα οποία υπάρχει σύντομο πιστοποιητικό για το ΟΧΙ (σε αντιστοιχία με την κλάση ΝΡ όπου υπάρχει σύντομο πιστοποιητικό για το ΝΑΙ – ανατρέξτε στην ενότητα 3.6 του Τόμου Β’). Για παράδειγμα, για το πρόβλημα SAT = {Φ | η Φ είναι μια Λογική έκφραση που είναι ικανοποιήσιμη}, το συμπληρωματικό του είναι το UNSAT = {Φ | η Φ είναι μια Λογική έκφραση που δεν είναι ικανοποιήσιμη}. Αφου SATÎNP, θα είναι UNSATÎcoNP. Τα coNP-πλήρη προβλήματα ορίζονται με τον συνήθη τρόπο (ανατρέξτε για παράδειγμα στον ορισμό 3.7 του Τόμου Β’).

Α) Δείξτε ότι εάν οι κλάσεις NP και coNP είναι διαφορετικές, τότε και οι κλάσεις P και NP είναι διαφορετικές.

Β) Δείξτε ότι εάν ένα πρόβλημα X είναι NP-πλήρες, τότε το συμπληρωματικό του, Χ’, είναι coNP -πλήρες.

Γ) Δείξτε ότι το πρόβλημα VSAT = {Φ | η Φ είναι μια Λογική έκφραση που ικανοποιείται από κάθε ανάθεση τιμών στις μεταβλητές της} ανήκει στην κλάση coNP.