Μάθημα : Υπολογιστική Πολυπλοκότητα

Καλησπέρα σε όλα,

Οι βαθμοί της εξεταστικής Εαρινού βρίσκονται στα Έγγραφα. Δεν έχει νόημα να μου γράψετε αν δεν διαβάσετε ή/και δεν σας βγάζουν νόημα τα παρακάτω:

1) Η μεγάλη πλειοψηφία των e-mail δεν θα απαντηθεί. Θα λειφθούν όλα τα αιτήματα υπόψιν.

2) Δεν θα υπάρξει επίδειξη γραπτών.

3) Δεν βλέπω e-mail που στέλνονται σε άλλη διεύθυνση πλην της jlivier89@math.uoa.gr.

4) Δεν υπάρχει απολύτως κανένας λόγος να στέλνετε περισσότερα του ενός e-mail, καθώς τσεκάρω το (κατά βάση μη λειτουργικό) spam folder μου.

5) Η ποσότητα χαρτιού και μελανιού που ξοδέψατε δεν σχετίζεται με το αν αυτά που γράφατε ήταν σωστά ή είχαν νόημα.

6) Προσπάθησα, όσο ήταν δυνατόν, να αγνοώ τις προσπάθειες που κάνατε να με πείσετε ότι δεν έχετε ιδέα για τι πράγμα γράφατε, και να περιορίζομαι στα κομμάτια των απαντήσεών σας που, τυχαία ή μη, ήταν σωστά.

7) Η (πολυωνιμική) μείωση και τα κάθε είδους σκληρά προβλήματα, δεν αποτελούν ορολογία του μαθήματος.

8) Το να παίρνετε ως υπόθεση το προς απόδειξη ζητούμενο, λέγεται "λήψη του ζητουμένου" ή "κύκλους κάνει το μυαλό μου" και δεν αποτελεί αποδεκτή αποδεικτική μέθοδο.

9) Όσα από εσάς αποδείξατε βάσει των όποιων υποθέσεων είχαν τα θέματα (ή χρησιμοποιήσατε ως γνωστό) ότι NP-δύσκολα προβλήματα επιδέχονται πολυωνυμικού χρόνου αλγορίθμους... δεν πήγε πολύ καλά η φάση.

10) Μία αναγωγή f από το Α στο Β, δεν μπορεί να προϋποθέτει γνώση και πρόσβαση στην απάντηση του ερωτήματος "w στο Α;" για να οριστεί το f(w). To f(w) πρέπει να ορίζεται ανεξάρτητα και κατάλληλα ώστε να ισχύει η ιδιότητα "w στο Α αν και μόνον αν f(w) στο Β".  

11) Δύο μη συνδεόμενες κορυφές, μπορούν να λάβουν το ίδιο χρώμα και δεν αυξάνουν τον χρωματικό αριθμό. Επίσης 2 ή 3 κορυφές συνδεόμενες με όλες τις υπόλοιπες του γραφήματος, ανεβάζουν υποχρεωτικά τον χρωματικό αριθμό. Το ίδιο ισχύει και με 4-κλίκες, αν είχαμε 3-χρωματισμό. Όλες αυτές οι αναγωγές δυστυχώς έχαναν τουλάχιστον την μία κατεύθυνση του "ανν" στο Θ2.

12) Όπως κι αν οριστεί ένας αριθμός Μ>0, και ανεξαρτήτως με το αν δύο αριθμοί Α,Β>0 είναι ίσοι ή όχι, ο ισχυρισμός ότι Α+Μ=Β+Μ=Μ έχει κάποιο πρόβλημα. Το ίδιο ισχύει και για τον ισχυρισμό ότι Α=Β=0=0=...=0. Ακόμη, αν ένα σύνολο S ισομερίζεται σε k-1 υποσύνολα ίσου αθροίσματος, ας πούμε Τ, το σύνολο (S,T,...,T), με το T k-1 φορές, έχει ισομερισμό σε k-1 υποσύνολα αθροίσματος 2Τ, ή σε 2k-2 υποσύνολα αθροίσματος Τ, πάντως όχι σε k υποσύνολα. Τέλος, το ότι n θετικοί ακέραιοι μπορούν να χωριστούν σε δύο σύνολα S, T, τ.ω. sum(S)=sum(T), δεν συνεπάγεται σε καμία περίπτωση ότι

||S|-|T||<=1, κι άρα το συμπέρασμα ότι αρκεί το πολύ ένα 0 ώστε να πάρουμε το |S|=|T| είναι λάθος. Τα παραπάνω μηδενίζουν όλο το Θ3, σε κόσμο που ίσως θεωρεί ότι το είχε πιάσει όλο.

13) Ασχέτως με το αν είχατε βάλει ρήτρα στο γραπτό σας, γράψτε μου αν θέλετε να μην κρατήσω τον βαθμό και να επανεξεταστείτε τον Σεπτέμβρη.

Παρακαλώ βοηθήστε με να ασχοληθώ όντως με περιπτώσεις που ενδέχεται να έχω βαθμολογήσει λάθος, και μην στέλνετε αιτήματα για αναβαθμολόγηση απλώς επειδή δεν χάνετε και τίποτα να το κάνετε. Το μάθημα είναι εξειδικευμένο και έχει ήδη εξαντληθεί η επιοίκεια στην διόρθωση που μπορώ να δείξω βάσει των περιορισμών που έχω.

Γιάννης