Πτυχίο πρωτοβάθμιο, κομπιουτεράς Λυκείου,
μα τελειωμένη έχω εγώ σχολή πεζοδρομίου...
Στη ζήση το πτυχίο μου, μ' έβαζε σε σαλόνια,
μα 'κεί 'ναι που θα έχανα φίλοι, τα παντελόνια...
Γι' αυτό και το πτυχίο μου, το κρέμασα στον τοίχο
και τση καρδιάς μου άκουσα τον δυνατό τον ήχο:
που μού 'λεγε να μην γενείς ρουφιάνος, ψεύτης, κλέφτης
να γίνεις ένας άνθρωπος, και τση ζωής λεβέντης...
Ποτέ σου, άλλου το κακό, μη θέλεις να ζητήσεις,
γιατί να είσαι σίγουρος, πως θα το συναντήσεις...
Να είσαι πάντα τίμιος με καθαρά τα χέρια,
ν' αστράφτει και το μέτωπο σαν φωτεινά αστέρια...
Έτσι λοιπόν η μοίρα μου μ' έκανε νταλικέρη,
για ν' αλητεύω λεύτερος, σ' αυτής της γής τα μέρη...
http://g-agios.blogspot.com/
Κυριακή 17 Ιανουαρίου 2010
Πέμπτη 14 Ιανουαρίου 2010
Οχι Στον Φασισμό !
ΟΧΙ στον φασισμό της βίας.
Να δοθεί τέρμα στις επιθέσεις σε πολίτες και μη αυτής της χώρας από όπου και εάν προέρχονται!
Οι ακροδεξιοί , οι ακροαριστεροί, οι κεντρώοι, οι αναρχικοί ή όποιοι άλλοι δε μου λένε τίποτα απολύτως!
Αν η ιδεολογία τους δε φτάνει στα αυτιά μας δε μπορεί "να μας κόβουν τα αυτιά" για να ακουστούν! Αν διαφωνούμε με αυτά που διαβάζουμε ή ακούμε δε μπορεί να μας το επιβάλλουν με τη βία!!!
Στην Ελλάδα μας ,μετά από τόσο αίμα που χύθηκε για να υπάρξει αυτή η δημοκρατία, πρέπει να προστατεύουμε το δικαίωμα στον διάλογο. Η ιστορία των Ελλήνων χάνεται πίσω πάνω από 3000 χρόνια επειδή ,παρότι ακούγεται "εθνικιστικό" ,είναι γεγονός πως εδώ ακούστηκαν αλήθειες, φιλοσοφίες, επιστήμες και δε φοβόντουσαν να αναπτύξουν διαφορετικές ιδέες για τις πέτρες τα βουνά και τόσα αλλά από τις επικρατούσες τότε ιδέες.
Ακούστηκε πως στην Ελλάδα υπάρχει συγκεκαλυμμένη δικτατορία!
Στην Ελλάδα λοιπόν πριν 100 μέρες έγιναν εκλογές.
Εκεί ο λαός μέτρησε τους υποψήφιους και αποφάσισε ποιόν ήθελε!
Αυτοί που τώρα με τρομακρατικά χτυπήματα θέλουν να μας επιβάλλουν απόψεις ΠΟΙΟΙ είναι και ΠΩΣ τολμούν!
Θα έπρεπε να ντρέπονται!
Ελαφρυντικό θεωρούν πως η επικρατούσα τάξη αποκλείει την ενημέρωση με φρέσκες ιδέες όμως η χούντα δεν έπεσε από τις "στρακαστρούκες" όπως χαρακτηριστικά έλεγε εκείνη η άλλη βλαμμένη ομάδα αλλά από τον αγώνα τον ιδεολογικό εντός και εκτός Ελλάδος.
ΥΓ
Με αφορμή τις επιθέσεις των καραγκιόζηδων σε Βουλή - σε στέκια μεταναστών - σε φοιτητές και καθηγητές πανεπιστημίων - σε κρατούμενους - στο κατάστημα του μπουμπούκου ;) και τόσα άλλα μέρη!
Να δοθεί τέρμα στις επιθέσεις σε πολίτες και μη αυτής της χώρας από όπου και εάν προέρχονται!
Οι ακροδεξιοί , οι ακροαριστεροί, οι κεντρώοι, οι αναρχικοί ή όποιοι άλλοι δε μου λένε τίποτα απολύτως!
Αν η ιδεολογία τους δε φτάνει στα αυτιά μας δε μπορεί "να μας κόβουν τα αυτιά" για να ακουστούν! Αν διαφωνούμε με αυτά που διαβάζουμε ή ακούμε δε μπορεί να μας το επιβάλλουν με τη βία!!!
Στην Ελλάδα μας ,μετά από τόσο αίμα που χύθηκε για να υπάρξει αυτή η δημοκρατία, πρέπει να προστατεύουμε το δικαίωμα στον διάλογο. Η ιστορία των Ελλήνων χάνεται πίσω πάνω από 3000 χρόνια επειδή ,παρότι ακούγεται "εθνικιστικό" ,είναι γεγονός πως εδώ ακούστηκαν αλήθειες, φιλοσοφίες, επιστήμες και δε φοβόντουσαν να αναπτύξουν διαφορετικές ιδέες για τις πέτρες τα βουνά και τόσα αλλά από τις επικρατούσες τότε ιδέες.
Ακούστηκε πως στην Ελλάδα υπάρχει συγκεκαλυμμένη δικτατορία!
Στην Ελλάδα λοιπόν πριν 100 μέρες έγιναν εκλογές.
Εκεί ο λαός μέτρησε τους υποψήφιους και αποφάσισε ποιόν ήθελε!
Αυτοί που τώρα με τρομακρατικά χτυπήματα θέλουν να μας επιβάλλουν απόψεις ΠΟΙΟΙ είναι και ΠΩΣ τολμούν!
Θα έπρεπε να ντρέπονται!
Ελαφρυντικό θεωρούν πως η επικρατούσα τάξη αποκλείει την ενημέρωση με φρέσκες ιδέες όμως η χούντα δεν έπεσε από τις "στρακαστρούκες" όπως χαρακτηριστικά έλεγε εκείνη η άλλη βλαμμένη ομάδα αλλά από τον αγώνα τον ιδεολογικό εντός και εκτός Ελλάδος.
ΥΓ
Με αφορμή τις επιθέσεις των καραγκιόζηδων σε Βουλή - σε στέκια μεταναστών - σε φοιτητές και καθηγητές πανεπιστημίων - σε κρατούμενους - στο κατάστημα του μπουμπούκου ;) και τόσα άλλα μέρη!
Τρίτη 5 Ιανουαρίου 2010
Ο αποκλεισμός των Τεμπών που δέ τον μάθαμε!!!
Οι εργολάβοι κυρίαρχοι των Τεμπών
Το μπλόκο των εργολάβων
Το σημείο «G» Ελλάδας, τα Τέμπη, έκλεισαν επ’ αόριστον. Τα θρυλικά Τέμπη του Κοκκινούλη, του Νασίκα, του Παττάκη και του Μπούτα, τα Τέμπη των σκασμένων ελαστικών και του «ρεσάλτου» του Χατζηγάκη στα τρακτέρ, τα Τέμπη του Σουφλιά, αλλά βασικά τα Τέμπη της Κοινοπραξίας Αυτοκινητόδρομος Αιγαίου ΑΕ, όλων δηλαδή των εθνικών εργολάβων μαζί, έκλεισαν για τα καλά και μάλιστα Χριστουγεννιάτικα, κάτω από τη βαριά σκιά ενός θανάτου. Χωρίς εξεταστικές, χωρίς εισαγγελικές έρευνες, χωρίς απαντήσεις στα ερωτήματα - βεβαιότητες που δημοσίευσε το "Ποντίκι". Με τους βασικούς τηλεοπτικούς σταρ και τις εφημερίδες τους να σφυρίζουν αδιάφορα και να παγιδεύουν με κομπιουτεράκια υπουργούς. Τα θρυλικά μπλόκα των Τεμπών, άλλοτε στο στόχαστρο των τηλεσχολιαστών, ωχριούν μπροστά στην επέλαση των βράχων.
Εκλεισαν τα Τέμπη και το άστρο της Βηθλεέμ έκανε το θαύμα του! Στην Ελλάδα ήρθε ο πολιτισμός: Ακόμα και με νεκρό, τα κανάλια συναγωνίστηκαν σε διακριτικότητα για την «πραγματική έκταση» της είδησης. Λίγες οι επί τόπου συνδέσεις όταν στα αγροτικά μπλόκα ξεροστάλιαζαν για μέρες οι ρεπόρτερ και ο Πάνος Σόμπολος. Πάρθηκαν γρήγορες αποφάσεις για τις παρακαμπτηρίους χωρίς να μείνουν οι φορτηγατζήδες με τα «ευπαθή» οι οποίοι ερχόντουσαν άλλοτε στα χέρια με τους αγρότες. Με τα "περάστε" και τα "προσέχετε" εξυπηρετούν τώρα τους οδηγούς οι 400 ευγενικοί τροχονόμοι. Κανένα πάνελ εξεγερμένων δημοσιογράφων για την ολική κατάρρευση του εθνικού δικτύου ακριβώς στον αδύναμο κρίκο του. Ούτε στα διεθνή ΜΜΕ πρώτη είδηση η Ελλάδα με τα κλειστά Τέμπη. Ο κόσμος ταλαιπωρείται ατέλειωτες ώρες στην Εθνική στα σιωπηλά! Για κάμποσους μήνες, και βλέπουμε. Ομως για είκοσι μόνο μέρες τα αγροτικά μπλόκα δημιουργούσαν το απόλυτο μονοθεματικό δελτίο και παράλληλα "την κατάλυση της έννομης τάξης".
Ποιός, όμως, μοίρασε και πώς τις άδειες στα Τέμπη δεν θα μάθουμε, ούτε γιατί δεν είχαν γίνει οι απαραίτητες επεμβάσεις εγκαίρως ούτε ποιοί τις εμπόδισαν. Αντίθετα, μόλις ολοκληρωθούν τα έργα θα αρχίσουμε να πληρώνουμε ακριβότερα διόδια. Αν έφταιγαν οι συνεχείς ανατινάξεις ή οι βροχές ή οι κακοτεχνίες ή οι «βολικές» μελέτες επικινδυνότητας ή τα πλημμελή μέτρα ασφάλειας για τη σήραγγα που εγκαινίασε ο θεσσαλός τέως υπουργός δεν απασχολεί ιδιαίτερα. Λίγο το πένθος για το θάνατο του Χρήστου Λαμπράκη, λίγο το πνεύμα των Χριστουγέννων, λίγο και η προσπάθεια «να μην διαταραχτεί ο κοινωνικός ιστός», ΜΜΕ και πολιτικοί κράτησαν «χαμηλούς τόνους».
Ας τα βλέπουν τώρα όλα αυτά οι πολίτες που άλλες φορές πείθονται τόσο εύκολα να στρέφονται κατά της κάθε κοινωνικής ομάδας που διαμαρτύρεται με διαδηλώσεις και καταλήψεις, ας τα βλέπει αυτά και ο αρμόδιος υπουργός, που ετοιμάζεται να μοιράσει νέα δημόσια έργα οδοποιίας, ώστε να πάρει τα μέτρα του με ρήτρες και διασφαλίσεις, διότι το σίγουρο είναι ότι το «θαύμα του πολιτισμού στην Ελλάδα» θα κρατήσει πολύ λίγο. Οσο για την Κοινοπραξία Αιγαίου που ρήμαξε -ως φαίνεται- τα Τέμπη κάτι ήξερε όταν επέλεγε επωνυμία μια και το αποτέλεσμα είναι "Σιγή Ιχθύος".
(Ελευθεροτυπία, 2/2/2010)
www.iospress.gr
Το μπλόκο των εργολάβων
Το σημείο «G» Ελλάδας, τα Τέμπη, έκλεισαν επ’ αόριστον. Τα θρυλικά Τέμπη του Κοκκινούλη, του Νασίκα, του Παττάκη και του Μπούτα, τα Τέμπη των σκασμένων ελαστικών και του «ρεσάλτου» του Χατζηγάκη στα τρακτέρ, τα Τέμπη του Σουφλιά, αλλά βασικά τα Τέμπη της Κοινοπραξίας Αυτοκινητόδρομος Αιγαίου ΑΕ, όλων δηλαδή των εθνικών εργολάβων μαζί, έκλεισαν για τα καλά και μάλιστα Χριστουγεννιάτικα, κάτω από τη βαριά σκιά ενός θανάτου. Χωρίς εξεταστικές, χωρίς εισαγγελικές έρευνες, χωρίς απαντήσεις στα ερωτήματα - βεβαιότητες που δημοσίευσε το "Ποντίκι". Με τους βασικούς τηλεοπτικούς σταρ και τις εφημερίδες τους να σφυρίζουν αδιάφορα και να παγιδεύουν με κομπιουτεράκια υπουργούς. Τα θρυλικά μπλόκα των Τεμπών, άλλοτε στο στόχαστρο των τηλεσχολιαστών, ωχριούν μπροστά στην επέλαση των βράχων.
Εκλεισαν τα Τέμπη και το άστρο της Βηθλεέμ έκανε το θαύμα του! Στην Ελλάδα ήρθε ο πολιτισμός: Ακόμα και με νεκρό, τα κανάλια συναγωνίστηκαν σε διακριτικότητα για την «πραγματική έκταση» της είδησης. Λίγες οι επί τόπου συνδέσεις όταν στα αγροτικά μπλόκα ξεροστάλιαζαν για μέρες οι ρεπόρτερ και ο Πάνος Σόμπολος. Πάρθηκαν γρήγορες αποφάσεις για τις παρακαμπτηρίους χωρίς να μείνουν οι φορτηγατζήδες με τα «ευπαθή» οι οποίοι ερχόντουσαν άλλοτε στα χέρια με τους αγρότες. Με τα "περάστε" και τα "προσέχετε" εξυπηρετούν τώρα τους οδηγούς οι 400 ευγενικοί τροχονόμοι. Κανένα πάνελ εξεγερμένων δημοσιογράφων για την ολική κατάρρευση του εθνικού δικτύου ακριβώς στον αδύναμο κρίκο του. Ούτε στα διεθνή ΜΜΕ πρώτη είδηση η Ελλάδα με τα κλειστά Τέμπη. Ο κόσμος ταλαιπωρείται ατέλειωτες ώρες στην Εθνική στα σιωπηλά! Για κάμποσους μήνες, και βλέπουμε. Ομως για είκοσι μόνο μέρες τα αγροτικά μπλόκα δημιουργούσαν το απόλυτο μονοθεματικό δελτίο και παράλληλα "την κατάλυση της έννομης τάξης".
Ποιός, όμως, μοίρασε και πώς τις άδειες στα Τέμπη δεν θα μάθουμε, ούτε γιατί δεν είχαν γίνει οι απαραίτητες επεμβάσεις εγκαίρως ούτε ποιοί τις εμπόδισαν. Αντίθετα, μόλις ολοκληρωθούν τα έργα θα αρχίσουμε να πληρώνουμε ακριβότερα διόδια. Αν έφταιγαν οι συνεχείς ανατινάξεις ή οι βροχές ή οι κακοτεχνίες ή οι «βολικές» μελέτες επικινδυνότητας ή τα πλημμελή μέτρα ασφάλειας για τη σήραγγα που εγκαινίασε ο θεσσαλός τέως υπουργός δεν απασχολεί ιδιαίτερα. Λίγο το πένθος για το θάνατο του Χρήστου Λαμπράκη, λίγο το πνεύμα των Χριστουγέννων, λίγο και η προσπάθεια «να μην διαταραχτεί ο κοινωνικός ιστός», ΜΜΕ και πολιτικοί κράτησαν «χαμηλούς τόνους».
Ας τα βλέπουν τώρα όλα αυτά οι πολίτες που άλλες φορές πείθονται τόσο εύκολα να στρέφονται κατά της κάθε κοινωνικής ομάδας που διαμαρτύρεται με διαδηλώσεις και καταλήψεις, ας τα βλέπει αυτά και ο αρμόδιος υπουργός, που ετοιμάζεται να μοιράσει νέα δημόσια έργα οδοποιίας, ώστε να πάρει τα μέτρα του με ρήτρες και διασφαλίσεις, διότι το σίγουρο είναι ότι το «θαύμα του πολιτισμού στην Ελλάδα» θα κρατήσει πολύ λίγο. Οσο για την Κοινοπραξία Αιγαίου που ρήμαξε -ως φαίνεται- τα Τέμπη κάτι ήξερε όταν επέλεγε επωνυμία μια και το αποτέλεσμα είναι "Σιγή Ιχθύος".
(Ελευθεροτυπία, 2/2/2010)
www.iospress.gr
Τετάρτη 30 Δεκεμβρίου 2009
Παρασκευή 25 Δεκεμβρίου 2009
Σάββατο 5 Δεκεμβρίου 2009
Μία εξέγερση που δέν υπήρξε!
Αξιοθαύμαστο στην Ελληνική ιστορία είναι πώς πολύς κόσμος θυμάται γεγονότα 2000 και 3000 χρόνια παλιά αλλά επιλέγει να ξεχνά κάτι που συνέβη πέρσι.
Πανελλαδικά εξεγέρθηκαν νέοι που δεν άντεξαν μία ΔΟΛΟΦΟΝΙΑ ενός παιδιού .
ΟΜΩΣ ο κόσμος θυμάται μόνο τα παρατράγουδα που συνέβησαν στο κέντρο της Αθήνας και επικάλυψαν την ισχύ και το αδιέξοδο των νέων ...
Εμείς δε πρέπει να ξεχάσουμε...
Πανελλαδικά εξεγέρθηκαν νέοι που δεν άντεξαν μία ΔΟΛΟΦΟΝΙΑ ενός παιδιού .
ΟΜΩΣ ο κόσμος θυμάται μόνο τα παρατράγουδα που συνέβησαν στο κέντρο της Αθήνας και επικάλυψαν την ισχύ και το αδιέξοδο των νέων ...
Εμείς δε πρέπει να ξεχάσουμε...
Πέμπτη 19 Νοεμβρίου 2009
Τετάρτη 18 Νοεμβρίου 2009
Ο Μικης Θεωδοράκης απαντά την μόνη άξια απάντηση στην τρομοκρατία που έχω ακούσει ...
«Λεβέντες μου σας καμαρώνω! Είστε οι συνεχιστές του Κολοκοτρώνη, του Ανδρούτσου και του Άρη σε σύγχρονη εκδοχή. Και γι' αυτό η τελευταία ελπίδα του προδομένου λαού μας. Με τη γενναία σας δημόσια αποκήρυξή μου, μου ανοίξατε τα μάτια. Ομολογώ, έστω και καθυστερημένα, ότι υπήρξα ένας ελεεινός και σιχαμερός προδότης-συνεργάτης της χούντας και της αντιλαϊκής δεξιάς και τώρα μετανοιωμένος αποζητώ τη δίκαιη τιμωρία μου.
Το σπίτι μου βρίσκεται σε μικρή πάροδο της οδού Γαριβάλδη, στην Επιφανους 1, και καθώς είμαι ξαπλωμένος έχω απέναντί μου την πλαγιά του Φιλοπάππου, απ' όπου σας είναι πανεύκολο να με κάψετε ζωντανό, για να με λυτρώσετε από τις τύψεις που με ζώνουν. Προς τούτο, έχω ορθάνοιχτα τα παράθυρα μου για να σας διευκολύνω με κίνδυνο να πάθω γρίπη.
Όμως, ποιος λογαριάζει τέτοιες λεπτομέρειες όταν έχει να κάνει με terroristes-τιμωρούς όπως εσείς;...
Je vous remercie»
ΥΓ. «Καημένε Παπαδόπουλε, πού είσαι να καμαρώσεις τη σπορά σου...».
Το σπίτι μου βρίσκεται σε μικρή πάροδο της οδού Γαριβάλδη, στην Επιφανους 1, και καθώς είμαι ξαπλωμένος έχω απέναντί μου την πλαγιά του Φιλοπάππου, απ' όπου σας είναι πανεύκολο να με κάψετε ζωντανό, για να με λυτρώσετε από τις τύψεις που με ζώνουν. Προς τούτο, έχω ορθάνοιχτα τα παράθυρα μου για να σας διευκολύνω με κίνδυνο να πάθω γρίπη.
Όμως, ποιος λογαριάζει τέτοιες λεπτομέρειες όταν έχει να κάνει με terroristes-τιμωρούς όπως εσείς;...
Je vous remercie»
ΥΓ. «Καημένε Παπαδόπουλε, πού είσαι να καμαρώσεις τη σπορά σου...».
Δευτέρα 9 Νοεμβρίου 2009
Explained: P vs. NP ή αλλιώς τρωφή για το μυαλό :)
Explained: P vs. NP
Science and technology journalists pride themselves on the ability to explain complicated ideas in accessible ways, but there are some technical principles that we encounter so often in our reporting that paraphrasing them or writing around them begins to feel like missing a big part of the story. So in a new series of articles called "Explained," MIT News Office staff will explain some of the core ideas in the areas they cover, as reference points for future reporting on MIT research.
In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a dark surface etched with green gridlines and strewn with geometric shapes, above which hover strange equations. One of these is the deceptively simple assertion that P = NP.
In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. Roughly speaking, P is a set of relatively easy problems, and NP is a set of what seem to be very, very hard problems, so P = NP would imply that the apparently hard problems actually have relatively easy solutions. But the details are more complicated.
Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.
Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: there’s no way around that. But if it simply keeps a record of the largest number it’s seen so far, it has to look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it’s handling — which computer scientists designate N. Of course, most algorithms are more complicated, and thus less efficient, than the one for finding the largest number in a list; but many common algorithms have execution times proportional to N2, or N times the logarithm of N, or the like.
A mathematical expression that involves N’s and N2s and N’s raised to other powers is called a polynomial, and that’s what the “P” in “P = NP” stands for. P is the set of problems whose solution times are proportional to polynomials involving N's.
Obviously, an algorithm whose execution time is proportional to N3 is slower than one whose execution time is proportional to N. But such differences dwindle to insignificance compared to another distinction, between polynomial expressions — where N is the number being raised to a power — and expressions where a number is raised to the Nth power, like, say, 2N.
If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N3 takes almost three hours. But an algorithm whose execution time is proportional to 2N takes 300 quintillion years. And that discrepancy gets much, much worse the larger N grows.
NP (which stands for nondeterministic polynomial time) is the set of problems whose solutions can be verified in polynomial time. But as far as anyone can tell, many of those problems take exponential time to solve. Perhaps the most famous problem in NP, for example, is finding prime factors of a large number. Verifying a solution just requires multiplication, but solving the problem seems to require systematically trying out lots of candidates.
So the question “Does P equal NP?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?” Part of the question’s allure is that the vast majority of NP problems whose solutions seem to require exponential time are what’s called NP-complete, meaning that a polynomial-time solution to one can be adapted to solve all the others. And in real life, NP-complete problems are fairly common, especially in large scheduling tasks. The most famous NP-complete problem, for instance, is the so-called traveling-salesman problem: given N cities and the distances between them, can you find a route that hits all of them but is shorter than … whatever limit you choose to set?
Given that P probably doesn’t equal NP, however — that efficient solutions to NP problems will probably never be found — what’s all the fuss about? Michael Sipser, the head of the MIT Department of Mathematics and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group (TOC), says that the P-versus-NP problem is important for deepening our understanding of computational complexity.
“A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says.
Similarly, Sipser says, “the excitement around quantum computation really boiled over when Peter Shor” — another TOC member — “discovered a method for factoring numbers on a quantum computer. Peter's breakthrough inspired an enormous amount of research both in the computer science community and in the physics community.” Indeed, for a while, Shor’s discovery sparked the hope that quantum computers, which exploit the counterintuitive properties of extremely small particles of matter, could solve NP-complete problems in polynomial time. But that now seems unlikely: the factoring problem is actually one of the few hard NP problems that is not known to be NP-complete.
Sipser also says that “the P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful. I think it has helped bridge the mathematics and computer science communities.”
But if, as Sipser says, “complexity adds a new wrinkle on old problems” in mathematics, it’s changed the questions that computer science asks. “When you’re faced with a new computational problem,” Sipser says, “what the theory of NP-completeness offers you is, instead of spending all of your time looking for a fast algorithm, you can spend half your time looking for a fast algorithm and the other half of your time looking for a proof of NP-completeness.”
Sipser points out that some algorithms for NP-complete problems exhibit exponential complexity only in the worst-case scenario and that, in the average case, they can be more efficient than polynomial-time algorithms. But even there, NP-completeness “tells you something very specific,” Sipser says. “It tells you that if you’re going to look for an algorithm that’s going to work in every case and give you the best solution, you’re doomed: don’t even try. That’s useful information.”
Science and technology journalists pride themselves on the ability to explain complicated ideas in accessible ways, but there are some technical principles that we encounter so often in our reporting that paraphrasing them or writing around them begins to feel like missing a big part of the story. So in a new series of articles called "Explained," MIT News Office staff will explain some of the core ideas in the areas they cover, as reference points for future reporting on MIT research.
In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a dark surface etched with green gridlines and strewn with geometric shapes, above which hover strange equations. One of these is the deceptively simple assertion that P = NP.
In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving. Roughly speaking, P is a set of relatively easy problems, and NP is a set of what seem to be very, very hard problems, so P = NP would imply that the apparently hard problems actually have relatively easy solutions. But the details are more complicated.
Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.
Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: there’s no way around that. But if it simply keeps a record of the largest number it’s seen so far, it has to look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it’s handling — which computer scientists designate N. Of course, most algorithms are more complicated, and thus less efficient, than the one for finding the largest number in a list; but many common algorithms have execution times proportional to N2, or N times the logarithm of N, or the like.
A mathematical expression that involves N’s and N2s and N’s raised to other powers is called a polynomial, and that’s what the “P” in “P = NP” stands for. P is the set of problems whose solution times are proportional to polynomials involving N's.
Obviously, an algorithm whose execution time is proportional to N3 is slower than one whose execution time is proportional to N. But such differences dwindle to insignificance compared to another distinction, between polynomial expressions — where N is the number being raised to a power — and expressions where a number is raised to the Nth power, like, say, 2N.
If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N3 takes almost three hours. But an algorithm whose execution time is proportional to 2N takes 300 quintillion years. And that discrepancy gets much, much worse the larger N grows.
NP (which stands for nondeterministic polynomial time) is the set of problems whose solutions can be verified in polynomial time. But as far as anyone can tell, many of those problems take exponential time to solve. Perhaps the most famous problem in NP, for example, is finding prime factors of a large number. Verifying a solution just requires multiplication, but solving the problem seems to require systematically trying out lots of candidates.
So the question “Does P equal NP?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?” Part of the question’s allure is that the vast majority of NP problems whose solutions seem to require exponential time are what’s called NP-complete, meaning that a polynomial-time solution to one can be adapted to solve all the others. And in real life, NP-complete problems are fairly common, especially in large scheduling tasks. The most famous NP-complete problem, for instance, is the so-called traveling-salesman problem: given N cities and the distances between them, can you find a route that hits all of them but is shorter than … whatever limit you choose to set?
Given that P probably doesn’t equal NP, however — that efficient solutions to NP problems will probably never be found — what’s all the fuss about? Michael Sipser, the head of the MIT Department of Mathematics and a member of the Computer Science and Artificial Intelligence Lab’s Theory of Computation Group (TOC), says that the P-versus-NP problem is important for deepening our understanding of computational complexity.
“A major application is in the cryptography area,” Sipser says, where the security of cryptographic codes is often ensured by the complexity of a computational task. The RSA cryptographic scheme, which is commonly used for secure Internet transactions — and was invented at MIT — “is really an outgrowth of the study of the complexity of doing certain number-theoretic computations,” Sipser says.
Similarly, Sipser says, “the excitement around quantum computation really boiled over when Peter Shor” — another TOC member — “discovered a method for factoring numbers on a quantum computer. Peter's breakthrough inspired an enormous amount of research both in the computer science community and in the physics community.” Indeed, for a while, Shor’s discovery sparked the hope that quantum computers, which exploit the counterintuitive properties of extremely small particles of matter, could solve NP-complete problems in polynomial time. But that now seems unlikely: the factoring problem is actually one of the few hard NP problems that is not known to be NP-complete.
Sipser also says that “the P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful. I think it has helped bridge the mathematics and computer science communities.”
But if, as Sipser says, “complexity adds a new wrinkle on old problems” in mathematics, it’s changed the questions that computer science asks. “When you’re faced with a new computational problem,” Sipser says, “what the theory of NP-completeness offers you is, instead of spending all of your time looking for a fast algorithm, you can spend half your time looking for a fast algorithm and the other half of your time looking for a proof of NP-completeness.”
Sipser points out that some algorithms for NP-complete problems exhibit exponential complexity only in the worst-case scenario and that, in the average case, they can be more efficient than polynomial-time algorithms. But even there, NP-completeness “tells you something very specific,” Sipser says. “It tells you that if you’re going to look for an algorithm that’s going to work in every case and give you the best solution, you’re doomed: don’t even try. That’s useful information.”
Εγγραφή σε:
Αναρτήσεις (Atom)