'Αλυτα μαθηματικά προβλήματα

[nouvelle vague]

Βλέποντας πως δεν υπάρχει στο forum κάποιο θέμα για τα άλυτα μαθηματικά προβλήματα είπα να ρίξω μια γρήγορη ματιά στο διαδίκτυο.
Έπεσα σε ένα ενδιαφέρον άρθρο για τα προβλήματα που βραβεύει το ινστιτούτο Clay.

1. Υπόθεση του Riemann: Υπάρχει συστηματικότητα στην κατανομή των πρώτων αριθμών - παραμένει άλυτη 148 χρόνια

Η ακολουθία των πρώτων αριθμών αρχίζει με τους 2,3, 5, 7 και 11. Όσο προχωράει κανείς στην ακολουθία, η συχνότητα τους μειώνεται, αλλά η κατανομή τους δεν παύει να παρουσιάζει μια συστηματοποίηση, που είναι γνωστή εδώ και αιώνες. Υπάρχουν, ωστόσο, μικρές παρεκκλίσεις, και το 1859 ο Bemhard Riemann υπέθεσε ότι θα μπορούσε να τις περιγράψει επακριβώς, αν κατάφερνε να αποδείξει την ύπαρξη μιας ξεχωριστής ιδιότητας για τις τιμές που μηδενίζουν μια συγκεκριμένη συνάρτηση. Πιο συγκεκριμένα, μια μιγαδική συνάρτηση που λέγεται ζήτα συνάρτηση του Riemann ζ(s), ορίζεται για όλους τους μιγαδικούς αριθμούς που είναι διάφοροι του 1. Η συνάρτηση αυτή μηδενίζεται για όλους τους άρτιους αρνητικούς αριθμούς. Δηλαδή για s=-2, s=-4, s=-6 κλπ. Οι τιμές αυτές μηδενισμού είναι οι τετριμμένες της λύσεις. H υπόθεση του Riemann αφορά τις μη τετριμμένες λύσεις και ισχυρίζεται ότι το πραγματικό μέρος όλων των μη τετριμμένων λύσεων που μηδενίζουν την ζήτα-συνάρτηση είναι το 1/2.  Η υπόθεση έχει επαληθευτεί για τις πρώτες 1.500.000.001 λύσεις, αλλά εξακολουθεί να λείπει η τελική απόδειξη.

2. Εικασία του Hodge: Μπορούν τα σχήματα να εξηγηθούν γεωμετρικά; - παραμένει άλυτη 70 χρόνια

Στον 20ο αιώνα οι μαθηματικοί ανακάλυψαν κάποιους δυναμικούς τρόπους για να ερευνήσουν τα σχήματα που είχαν κάποια πολύπλοκα αντικείμενα. Στην τεχνολογία π.χ. τρισδιάστατων γραφικών χρησιμοποιούνται απλά γεωμετρικά δομικά στοιχεία (κύκλοι, τρίγωνα και τετράγωνα) για να δημιουργηθούν πολύπλοκες γραφικές παραστάσεις - όπως, π.χ., η Lara Kraft στο Tomb Raider.
Η βασική ιδέα που είχε τη δεκαετία του 1930 (πολύ πριν εμφανιστούν τα ηλεκτρονικά παιγνίδια), ο Σκωτσέζος μαθηματικός William Hodge είναι ήταν να αναρωτηθεί μέχρι ποιο σημείο μπορούμε να προσεγγίσουμε το σχήμα ενός δεδομένου αντικειμένου, συγκολλώντας απλούς γεωμετρικούς δομικά στοιχεία με όλο και μεγαλύτερο μέγεθος. Το ερώτημα μάλιστα αυτό τέθηκε όχι μόνο για τον 3-διάστατο κόσμο αλλά και για περισσότερες διαστάσεις.
Η τεχνική αυτή της συγκόλλησης αποδείχτηκε μεγάλης χρησιμότητας, ώστε να γενικευτεί κατά πολλούς τρόπους και να μας δώσει προοδευτικά ισχυρά εργαλεία με τα οποία οι μαθηματικοί πέτυχαν την ταξινόμηση των διαφόρων σχημάτων που συναντούσαν κατά τις έρευνές τους.
Ατυχώς, οι γεωμετρικές καταβολές αυτής της διαδικασίας έγιναν τελείως δυσδιάκριτες καθώς εξελισσόταν η γενίκευση αυτή. Κατά κάποια έννοια, χρειαζόταν να προσθέσουμε κομμάτια που δεν είχαν καμιά γεωμετρική σημασία.
Η εικασία του Hodge ισχυρίζεται ότι για μερικούς ιδιαίτερης μαθηματικής κομψότητας χώρους, που λέγονται προβολικές αλγεβρικές κλάσεις, τα κομμάτια που χρειάζονται να συγκολληθούν και αποκαλούνται κύκλοι Hodge είναι  ρητοί γραμμικοί συνδυασμοί κομματιών που έχουν γεωμετρική σημασία και λέγονται αλγεβρικοί κύκλοι.  

3. P versus NP: Υπάρχει μια ιδανική διάταξη συνδαιτυμόνων; - παραμένει άλυτη 30 χρόνια

Υποθέστε ότι πρέπει να κάνετε μια λίστα για το πώς θα καθίσουν οι καλεσμένοι σε ένα μεγάλο εορταστικό δείπνο. Έχετε 400 άτομα στον κατάλογο σας, αλλά πρέπει να επιλέξετε μόνο 100 από αυτούς, καθώς δεν υπάρχει χώρος για περισσότερους. Επίσης, έχετε άλλη μια λίστα από ζεύγη αυτών των ανθρώπων, κι έτσι κανένα από αυτά τα ζευγάρια δεν πρέπει να εμφανιστεί στον τελικό κατάλογο των καλεσμένων που θα καθίσουν στο τραπέζι.

Το πρόβλημα αυτό είναι ένα παράδειγμα από αυτά που η πληροφορική αποκαλεί ΝΡ προβλήματα. Είναι εύκολο να ελέγξουμε αν μια συγκεκριμένη λίστα 100 ατόμων από τους 400 ικανοποιεί το κριτήριό μας να μην υπάρχουν ασύμβατα μεταξύ τους ζευγάρια στο τραπέζι. Το να δημιουργήσουμε όμως εμείς μια τέτοια λίστα από τους 400 είναι τόσο δύσκολο που μοιάζει να μην  είναι πρακτικά δυνατόν. Μάλιστα, ο αριθμός των εναλλακτικών τρόπων που μπορούμε να πάρουμε 100 καλεσμένους από τους 400 είναι μεγαλύτερος από το σύνολο των ατόμων που υπάρχουν στο σύμπαν, γι' αυτό και το πρόβλημα δε θα μπορούσε να λυθεί ούτε καν με τη βοήθεια του ισχυρότερου υπερυπολογιστή στον κόσμο.

Μπορεί όμως η δυσκολία αυτή να δείχνει απλά ότι προσεγγίζουμε προγραμματιστικά το πρόβλημα με λάθος μέθοδο. Υπάρχει άραγε ένας έξυπνος τρόπος να λυθεί το πρόβλημα; Το πρόβλημα αυτού του τύπου, «Ρ versus ΝΡ» -όπως λέγεται- εμφανίστηκε τη δεκαετία του 1970.  Οι Stephen Cook και Leonid Levin διατύπωσαν αυτό το πρόβλημα όπου το Ρ σημαίνει εύκολο να βρεθεί λύση και το ΝΡ σημαίνει εύκολο να ελεγχθεί, ανεξάρτητα ο ένας από τον άλλο κατά το 1971. Γενικά, έχει να κάνει με το αν όντως υπάρχουν προβλήματα τα οποία είναι εύκολο να ελεγχθούν αλλά πρακτικά αδύνατο να λυθούν με άμεσες αλγοριθμικές διαδικασίες.

Για προβλήματα όπως το παραπάνω, κανείς μέχρι σήμερα δεν έχει καταφέρει να δείξει ότι η λύση τους δεν είναι εφικτή με κατάλληλη προγραμματιστική μέθοδο.
Το πρόβλημα «Ρ versus NP» είναι θεμελιώδες για την ασφάλεια των υπολογιστών. Κι αυτό γιατί, όταν κρυπτογραφούνται ψηφιακά οι χρηματικές συναλλαγές, χρησιμοποιούνται αλγόριθμοι των οποίων η λύση ελέγχεται εύκολα αλλά δύσκολα βρίσκεται - μεταξύ άλλων, με κλειδιά κρυπτογράφησης που περιέχουν πρώτους αριθμούς. Αν αποδειχθεί ότι ένας ικανός προγραμματιστής μπορεί να βρει ένα σύντομο δρόμο για τη λύση τους, τότε το «σπάσιμο» της κρυπτογράφησης των πληρωμών με πιστωτικές κάρτες ίσως καταστεί εφικτό.

4. Εικασία των Birch και Swinnerton-Dyer: Πόσες ακέραιες λύσεις έχει π.χ. η εξίσωση ψ2=x2-x+1; Παραμένει άλυτη 40 χρόνια

Οι μαθηματικοί γοητεύονταν πάντα από την εύρεση όλων των λύσεων στο πεδίο των ακεραίων αριθμών, εξισώσεων όπως η παρακάτω  x2 + ψ2 = z2,    όπου οι x, ψ και z είναι ακέραιοι αριθμοί. Μια λύση είναι η 32 + 42=52. Εδώ και πάνω από 2.000 χρόνια, ο Ευκλείδης Βρήκε ένα γενικό τύπο που δίνει όλες τις πιθανές λύσεις (είναι άπειρες), αλλά σε πιο περίπλοκες εξισώσεις η εύρεση όλων των λύσεων είναι πράγμα εξαιρετικά δύσκολο. Στα 1970 ο Yu. V. Matiyasevich έδειξε ότι το 10ο πρόβλημα του Hilbert είναι αδύνατο. Δηλαδή έδειξε ότι δεν υπάρχει γενική μέθοδος που να μας δείχνει πότε οι εξισώσεις αυτές έχουν λύση στο πεδίο των ακεραίων αριθμών.

Ωστόσο, είναι σημαντικό να μπορεί κανείς να εκτιμήσει αν υπάρχει ένας πεπερασμένος ή άπειρος αριθμός λύσεων με ακέραιους αριθμούς για μια δεδομένη εξίσωση.
Ας πάρουμε για παράδειγμα τις λεγόμενες ελλειπτικές καμπύλες. Βασικά θα μπορούσαμε να πούμε ότι πρόκειται για αλγεβρικές εξισώσεις σαν την παρακάτω  y2 = x3 + ax + b, που ορίζουν επιφάνειες στο χώρο με μορφή σαμπρέλας.  

Κάθε ελλειπτική καμπύλη είναι μια αβελιανή ομάδα και τα σημεία πάνω σ' αυτήν με συντεταγμένες ρητούς αριθμούς σχηματίζουν μια υποομάδα. Πότε υπάρχουν άπειρα τέτοια ρητά σημεία; Στα 1965 οι Birch και Swinnerton-Dyer ισχυρίστηκαν ότι υπάρχει ένα κριτήριο που περιλαμβάνει ένα μαθηματικό αντικείμενο που λέγεται L-συνάρτηση της ελλειπτικής καμπύλης.  Η εικασία των  Birch-Swinnerton-Dyer λέει ότι L(1) = 0 αν και μόνο αν η ελλειπτική καμπύλη έχει άπειρα ρητά σημεία. Αν δηλαδή L(1) = 0 τότε υπάρχουν άπειρα ρητά σημεία επί της καμπύλης ή με άλλα λόγια άπειρες λύσεις της παραπάνω εξίσωσης. Ενώ αντίστροφα αν L(1) δεν ισούται με μηδέν τότε υπάρχει μόνο πεπερασμένος αριθμός ρητών λύσεων της εξίσωσης.

Αν μπορούσε να αποδειχτεί αυτή η εικασία θα έριχνε πολύ φως και στη λύση των Διοφαντικών εξισώσεων, μια από τις οποίες ανάγεται στον 10ο αιώνα μ.Χ. και στην οποία ζητείται να βρεθούν ποιοι ακέραιοι αριθμοί μπορούν να εμφανιστούν ως εμβαδά ορθογωνίων τριγώνων, των οποίων οι πλευρές έχουν ως μήκη ρητούς αριθμούς.

5. Το χάσμα μάζας στη θεωρία Yang-Mills: Παραμένει μαθηματικά αναπόδεικτο εδώ και 43 χρόνια

Οι νόμοι της κβαντικής φυσικής αποτελούν για τον κόσμο των στοιχειωδών σωματίων ότι οι νόμοι του Νεύτωνα για την κλασσική μηχανική του μακροσκοπικού κόσμου.Περίπου μισό αιώνα πριν, οι φυσικοί Chen Ning Yang και Robert Mills παρουσίασαν ένα νέο πλαίσιο για τη περιγραφή των στοιχειωδών σωματιδίων. Σ' αυτό χρησιμοποίησαν δομές που συναντάμε επίσης και στην γεωμετρία.

Η θεωρία Yang-Mills, όπως είναι γνωστή, αποτελεί πλέον τη βάση σχεδόν όλου του οικοδομήματος της σύγχρονης φυσικής των στοιχειωδών σωματιδίων, σύμφωνα με το Καθιερωμένο Πρότυπο. Το Καθιερωμένο Πρότυπο περιγράφει τις τρεις από τις τέσσερις αλληλεπιδράσεις που υπάρχουν στη φύση, δηλαδή τις ηλεκτρομαγνητικές, τις ασθενείς (αυτοί οι δύο τύποι αλληλεπιδράσεων έχουν ενοποιηθεί ως ηλεκτρασθενείς αλληλεπιδράσεις) και τις ισχυρές, που περιγράφονται από την κβαντική χρωμοδυναμική. Οι προβλέψεις της έχουν ελεγχθεί σε πολλά εργαστήρια αλλά παρόλα αυτά το μαθηματικό υπόβαθρο πάνω στο οποίο βασίζεται η θεωρία Yang-Mills παραμένει ασαφές.

Πιο συγκεκριμένα, η επιτυχής χρήση της θεωρίας Yang-Mills για την περιγραφή των ισχυρών αλληλεπιδράσεων εξαρτάται από μια λεπτή κβαντομηχανική ιδιότητα που είναι γνωστό τεχνικά ως χάσμα μάζας. Αυτό σημαίνει ότι πρέπει η πιο ελαφριά κατάσταση του ενός σωματιδίου ενός κβαντικού πεδίου στις 4 διαστάσεις, να έχει αυστηρά θετική μάζα.   Η ιδιότητα αυτή δεν έχει αποδειχτεί ακόμα μέσα στα πλαίσια της αυστηρής μαθηματικής θεμελίωσης της θεωρίας.

6. Εξισώσεις Navier-Stokes: Μπορούν να περιγραφούν τα κύματα; παραμένει άλυτη εδώ και 150 χρόνια

Οι εξισώσεις Navier-Stokes είναι ένα σύνολο εξισώσεων οι οποίες περιγράφουν την κίνηση των ρευστών όπως είναι τα υγρά και τα αέρια. Οι εξισώσεις αυτές μας λένε πως οι μεταβολές στην ορμή ενός απειροστού όγκου του ρευστού είναι απλά το αθροιστικό αποτέλεσμα των δυνάμεων ιξώδους του ρευστού, των μεταβολών της πίεσης, της βαρύτητας και των άλλων δυνάμεων που δρουν εντός του ρευστού. Πρόκειται στην ουσία για εφαρμογή του 2ου νόμου του Νewton στα ρευστά. Αφορούν δηλαδή τη δυναμική της αλληλεπίδρασης της αδράνειας του ρευστού με τις διάφορες δυνάμεις που δρουν σε μια περιοχή του ρευστού.
Είναι από τα πιο χρήσιμα σύνολα εξισώσεων γιατί εφαρμόζονται σε μοντέλα καιρού, μοντέλα ωκεάνιων ρευμάτων, ροή ρευστών σε σωλήνες, ροή αέρα γύρω από πτέρυγες αεροπλάνων και ανεμογενητριών, κίνηση άστρων μέσα στο γαλαξία κ.ο.κ.  Σε συνδυασμό εξάλλου με τις εξισώσεις Maxwell μπορούν να χρησιμοποιηθούν για να κάνουμε εξομοιώσεις και μα μελετήσουμε μοντέλα μαγνητοϋδροδυναμικής.

Οι εξισώσεις Navier-Stokes είναι διαφορικές εξισώσεις. Σε αντίθεση δηλαδή με τις αλγεβρικές εξισώσεις δεν μας δείχνουν εκπεφρασμένα μια σχέση μεταξύ των μεγεθών που μας ενδιαφέρουν (π.χ. μεταξύ ταχύτητας και πίεσης) αλλά περιγράφουν σχέσεις μεταξύ των ρυθμών μεταβολής ή μεταξύ των ροών των διαφόρων μεγεθών. Με όρους μαθηματικούς λέμε ότι οι εξισώσεις αυτές περιέχουν σχέσεις μεταξύ των παραγώγων των διαφόρων μεγεθών. Για παράδειγμα, οι εξισώσεις Navier-Stokes για την πιο απλή περίπτωση ενός ιδανικού ρευστού (χωρίς ιξώδες) μας λέει ότι η επιτάχυνση δηλ. η παράγωγος της ταχύτητας είναι ανάλογη με τη βαθμίδα (δηλ. την παράγωγο ως προς τις 3 χωρικές συντεταγμένες) της εσωτερικής πίεσης του ρευστού.

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

Για πιο περίπλοκες καταστάσεις, όπως είναι τα παγκόσμια συστήματα καιρού σαν το φαινόμενο El Nino, οι λύσεις των εξισώσεων Navier-Stokes πρέπει να βρεθούν με τη βοήθεια υπολογιστών. Πράγματι, έχει αναπτυχθεί μια ποικιλία υπολογιστικών προγραμμάτων που χρησιμοποιούν αριθμητικές μεθόδους για τη λύση των εξισώσεων Navier-Stokes.  Η προσέγγιση αυτή της αντιμετώπισης του ζητήματος είναι γνωστή ως Υπολογιστική Δυναμική των Ρευστών (CFD). Αν και θεωρητικά η CFD δουλεύει σε κάθε περίπτωση ροής, πολλές συνηθισμένες περιπτώσεις ροής όπως είναι η ροή γύρω από μια πτέρυγα αεροπλάνου, περιέχει τόσο πολλές λεπτομέρειες που κανένα πρόγραμμα υπολογιστή δεν μπορεί να λύσει το πρόβλημα σε λογικό χρονικό διάστημα.

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

http://www.physics4u.gr/articles/2007/u ... blems.html

Προφανώς υπάρχουν και πολλά άλλα όπως η εικασία του Goldbach:
Κάθε άρτιος θετικός ακέραιος μεγαλύτερος του 2 μπορεί να γραφτεί ως άθροισμα δύο πρώτων αριθμών, έτσι ώστε για κάθε n ≧ 2, 2n = p + q, όπου p, q πρώτοι αριθμοί.

Θα έβρισκα αρκετά ενδιαφέρον να συμπληρωνόταν η λίστα με περισσότερα άλυτα προβλήματα.

Offtopic:Πρώτο μου post με τόνους

[amadeus]

Ωραίο θέμα... Στο χέρι μας είναι να προσφέρουμε κάτι προς τη λύση τους..

[silverstar]

Φρέσκο: P≠NP!

Αυτός: http://en.wikipedia.org/wiki/Vinay_Deolalikar
έγγραψε αυτό: http://www.hpl.hp.com/personal/Vinay_De ... pdated.pdf
ισχυρίζοντας πως P≠NP.

Μένει να ελεγχθεί ο ισχυρισμός... Πάντως τα αρχικά σχόλια και οι εντυπώσεις είναι θετικές.
Χωρίς αυτό να σημαίνει πως λείπει και ο αντίλογος.

http://rjlipton.wordpress.com/2010/08/0 ... 2%89%A0np/
και οι πιο σκεπτικοί: http://scottaaronson.com/blog/?p=456

[pan]

Για όποιον Μαθηματικό πορωμένο ενδιαφέρεται, ορίστε ολόκληρη η δημοσίευση της φερόμενης ως "απόδειξης" P≠NP , του Deolalikar. Ας βρούμε κανά λάθος,μη μας φάει τα λεφτά παιδιά! Πάντως αν γίνει δεχτή ως απόδειξη, θα είναι φοβερό, τόσο από Μαθηματική, τεχνολογική, αλλά και φιλοσοφική - με την ευρύτερη έννοια - σκοπιά .

http://www.hpl.hp.com/personal/Vinay_De ... ated_1.pdf

[palasso]

Για την εξέλιξη αυτού του paper μπορείτε να επισκέπτεσθε το wiki: http://michaelnielsen.org/polymath1/ind ... s_NP_paper

[antony07]

Μην ενθουσιάζεστε (ακόμα), δυστυχώς υπάρχουν σοβαρά θέματα με την απόδειξη, και την χρήση των διαφόρων εργαλείων (κυρίως Λογικής) που χρησιμοποιεί. Δείτε εδώ.

Από ιστορικής σκοπιάς, όμως, υπάρχει ελπίδα. Λάθη είχαν βρεθεί και στην απόδειξη του Wiles, to 1994, τα οποία διόρθωσε ο ίδιος μετά από κάποιο καιρό, και η απόδειξη έγινε τελικά δεκτή από την κοινότητα.

Στέι τιούν'ντ!!

[antony07]

Ένα χρόνο μετά, η απόδειξη παραμένει στάσιμη. Διάφοροι ειδικοί, όπως ο Neil Immerman, βρίσκουν λάθη στα λογικά εργαλεία που χρησιμοποίησε ο Deolalikar (ένας υποκλάδος που λέγεται finite model theory ή descriptive complexity, που ασχολείται κυρίως με λογικούς χαρακτηρισμούς κλάσεων πολυπλοκότητας), τα οποία δεν έχουν "σουλουπωθεί" μέχρι τώρα...

Παραθέτω ενα άρθρο από το blog του R J Lipton (καθηγητή στο GeorgiaTech):

Deolalikar’s Claim: One Year Later


till no final chapter, lessons learned


Vinay Deolalikar just over a year ago claimed that he had a proof that .

Today I want to make a short comment on the status of his claim.
I recently received an email asking: Has the anniversary slipped your notice?
No. But there is not a lot to say about the situation—for better or for worse. Here is all that we know publicly:

• His web page still claims the result, and explains that it is out to a journal for the standard refereeing process.
• A few weeks ago when I inquired “what is up with the proof,” his e-mail reply said the same thing. He still believes that he has a proof, and reiterated that it is being checked by referees.
• He has expanded and updated the paper, and claims to have answered all the issues that were raised on the web here and elsewhere.
• He will not let the public see his proof, nor will he post it, so it remains an unknown.

Lessons

Ken and I learned several lessons from last year’s event.

• There is immense interest in the problem. This surprised us to some degree. We know the problem is important, is intriguing, and is hard. But we had no idea that so many people would be interested in the prospect of a proof.
• There is immense power in the web as a method of understanding mathematical claims. The proof attempt was read by many, and this quickly led to insights about it. From Fields Medalists to professional mathematicians to amateurs, all helped with the analysis of the claim. We were amazed at the power of the crowd in this situation.
• There is immense difficulty in explaining a new proof, especially for someone who primarily works in another area. We believe that Vinay’s main area of expertise is not computational complexity. Thus, it is to be expected that he might have trouble in quickly explaining the key insight that could make his proof work. Perhaps more immediately, this may cause trouble understanding the objections raised.
• The online community desires quick reactions and assessments. However, intricate mathematical arguments by their nature do not allow for them. What happens is that every word acquires a very high “slope.” Change the perceived meaning of a phrase a little from the intended meaning, and you have a wide difference in collective understanding. This happened with the word “serious” and even the word “proof” itself. The same slope applied to our own ethical decisions about presentation, not always to everyone’s liking.
• There is joy in grappling with new challenges, and feeling that others in a world community are pulling with you. This is so even if the evaluation of these challenges finds flaws in their ultimate objective. It is a realm where intellectual honesty prevails, and that is the gold standard of our field. This and our second point above were the aspects noted by popular author Steven Landsburg here.

A Worry

My biggest worry about all this is that claims of a major result should be resolved in a timely fashion, since otherwise unpleasant claims of credit and priority may arise.

I worked years ago on an open problem in the area of decision procedures. I proved an EXPSPACE lower bound on the so called Vector Addition Reachability Problem. See my earlier discussion for the details. While I proved a lower bound, for quite a while there was no upper bound—the problem could have been undecidable.

Here is what I said happened: (The proofs are of the decidability of the problem.)

"In act II, two proofs were found: the first by Ernst Mayr and shortly thereafter a proof by Rao Kosaraju. Many did not believe Mayr’s proof, since it was unclear in many places. Understanding these long complex arguments, with many interlocking definitions and lemmas, is difficult. Kosaraju created his proof because he felt Mayr’s proof was wrong. You can imagine there was an immediate controversy. Which proof was right? Both? Neither? There were claims that Kosaraju’s proof was essentially Mayr’s proof, but written in a clear way. The controversy got messy very quickly.

Finally, in act III there is now a new proof by Jérôme Leroux that seems much cleaner. and more likely to be correct. More on this in the future. "


I would hate to see this happen with the much more important problem of . I also notice that I still owe a discussion of Leroux’s proof that the problem is decidable. Oh well.

Of course, unlike the vector-addition case, there is no compelling sign of a proof here. However, there may be substantial contributions, perhaps new conditional results, that can possibly come from the work. This may be where the worry most applies. If there is something in Vinay Deolalikar’s long paper, then this is worth attending to, and the first onus is on the author.


Open Problems

How should we remember the event last year? Are there other lessons to be taken away?

Πηγή: http://rjlipton.wordpress.com/2011/08/1 ... ear-later/