P!=NP αποδείχθηκε;

[woochoogirl]

Δεν ξέρω αν το πήρατε χαμπάρι αλλά εδώ και δυο μέρες έχει γίνει ένας ψιλοπανικός με τη δήλωση του Vinay Deolalikar ότι απέδειξε ότι P ειναι διάφορο του NP.

Κανένας με επαρκείς γνώσεις που να μπορεί να τοποθετηθεί επί του θέματος; Πάω να σπαμάρω και κάποιους θεωρητικους καθηγητές μου, να δω τι θα μου πουν

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Γιώργος]

Το ίδιο πράγμα είδα κι εγώ σήμερα, σε αυτό το λινκ.

Το μόνο σχόλιο που 'χω να κάνω είναι πως μακάρι να είναι σωστός. Γιατί δεν θέλουμε με τίποτα να δειχθεί το αντίθετο, P=NP, γιατί τότε σπάει όλη η θεωρία της κρυπτογράφησης που βασίζεται στο ότι ένας brute-force αλγόριθμος που δοκιμάζει να σπάσει ένα δυνατό κλειδί πρακτικά δεν θα τερματίσει ποτέ.

Χώρια που αν το paper του έλεγε "απέδειξα ότι P=NP" θα τον ψάχναμε σήμερα σε κάνα χαντάκι...

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[woochoogirl]

Έστειλα κατενθουσιασμένη στον supervisor μου και με γειωσε πως ειναι σε διακοπες, πως ειναι αδυνατο να διαβασει 100 σελιδες και να μου τις εξηγησει με τη μια, και πως θα παρει καιρο η εξεταση της ολης αποδειξης. Αυτός μου γράφει πως είναι απαισιόδοξος, ο δικός του supervisor λέει πάλι πως θέλει να πιστεύει πως ισχύει. Ποιος ξέρει;
Μακαρι να'ναι παντως (αν και συμφωνω με τον Lipton σε αυτό το blog post , θα ήταν τρομακτικες οι συνεπειες, αλλα ακρως απροβλεπτες και ενδιαφερουσες μιας και κοινή πεποιθηση εστω και χωρις αποδειξη αποτελει το P!=NP), θα δώσει τρομερο boost στο θεωρητικό κομμάτι και ποιος ξέρει τι έρευνα θα γεννηθεί γύρω από αυτό.

Χώρια που αν το paper του έλεγε "απέδειξα ότι P=NP" θα τον ψάχναμε σήμερα σε κάνα χαντάκι...

Θυμάμαι που είχα διαβάσει πρόσφατα κάτι αντίστοιχο και μου είχε φανεί τραγικά τρομακτικό. Σίγουρα πολλές μεγαλοεταιρίες δεν τις συμφέρει μια τέτοια απόδειξη.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Rempeskes]

Please note that the final version of the paper is under preparation, and is to be posted here shortly (in about a week). Stay tuned.

Κόβω τον μισθο μου ότι α) μας δουλεύει β) η "συνοπτική απόδειξη" κάνει σιωπηρή παραδοχή μίας εκ των εκδοχών του p=np.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[tulip]

Αν όντως ο Deolalikar τα κατάφερε, αυτή θα είναι η δεύτερη λύση ενός από τα Millennium Prize Problems, και όλα αυτά μέσα σε μερικούς μήνες!
Εδώ για info και για την απόδειξη.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[woochoogirl]

Φανταζομαι πως θα το δεχθει αυτός το βραβειο

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Γιώργος]

Θυμάμαι που είχα διαβάσει πρόσφατα κάτι αντίστοιχο και μου είχε φανεί τραγικά τρομακτικό. Σίγουρα πολλές μεγαλοεταιρίες δεν τις συμφέρει μια τέτοια απόδειξη.

Έχεις λινκ;

Κόβω τον μισθο μου ότι α) μας δουλεύει β) η "συνοπτική απόδειξη" κάνει σιωπηρή παραδοχή μίας εκ των εκδοχών του p=np.

Έχεις μισθό;

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Guest 990498]

Έχω την απάντηση στο ερώτημα
εδώ και πολύ καιρό
αλλά δε δύναμαι να μιλήσω
χωρίς τη παρουσία του δικηγόρου μου.


πς: συμφωνεί μαζί μου και ο Γκριγκόρι Πέρελμαν.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[woochoogirl]

Μάλλον στο PopCo το'χα διαβασει.
Παντως ηδη εχουν πεσει οι πρωτες αντιρρησεις για το paper

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Rempeskes]

Κόβω τον μισθο μου ότι α) μας δουλεύει β) η "συνοπτική απόδειξη" κάνει σιωπηρή παραδοχή μίας εκ των εκδοχών του p=np.

Εδώ τελικά είχες δίκιο όταν επέμενες. Η "απόδειξη" είναι εσφαλμένη γιατί κάνει πάνω από μία παραδοχές διαφόρων εκδοχών του αποδεικτέου. Θα μου πείς "έτσι γίνεται με τα μεγάλα προβλήματα" και εγώ θα σου απαντούσα "μα και με τις ιντερνετικές διακηρύξεις".

Βέβαια ένας τρίτος θα έλεγε "πάει τα έχασε, με τον εαυτό του μιλάει".

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Γιώργος]

Εδώ τελικά είχες δίκιο όταν επέμενες. Η "απόδειξη" είναι εσφαλμένη γιατί κάνει πάνω από μία παραδοχές διαφόρων εκδοχών του αποδεικτέου. Θα μου πείς "έτσι γίνεται με τα μεγάλα προβλήματα" και εγώ θα σου απαντούσα "μα και με τις ιντερνετικές διακηρύξεις".

Βέβαια ένας τρίτος θα έλεγε "πάει τα έχασε, με τον εαυτό του μιλάει".

Δώσε λινκ.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[woochoogirl]

Kυκλοφορει εδω και καιρο το οτι απορριφθηκε. Ο ιδιος βεβαια λεει πως διορθωσε το λαθος και οτι το εχει καταθεσει αλλα μαλλον ο ρεμπεσκες εχει δικιο...
https://en.wikipedia.org/wiki/P_versus_NP_problem#Claimed_solutions

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Mr Positive]

Στην επίσημη ιστοσελίδα πάντως, συνεχίζει να εμφανίζεται ως άλυτο!

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[giannis4ever]

Τι ακριβώς είναι αυτό το P!=NP?

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Γιώργος]

Τι ακριβώς είναι αυτό το P!=NP?

Να εξετάσουμε αν ο χώρος των προβλημάτων που λύνονται σε πολυωνυμικό χρόνο από ντετερμινιστικά αυτόματα ταυτίζεται ή όχι με τον χώρο τον προβλημάτων που λύνονται σε πολυωνυμικό χρόνο από μη-ντετερμινιστικά αυτόματα.


Ήμουν σαφής, πιστεύω.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[antwwwnis]

Να εξετάσουμε αν ο χώρος των προβλημάτων που λύνονται σε πολυωνυμικό χρόνο από ντετερμινιστικά αυτόματα ταυτίζεται ή όχι με τον χώρο τον προβλημάτων που λύνονται σε πολυωνυμικό χρόνο από μη-ντετερμινιστικά αυτόματα.


Ήμουν σαφής, πιστεύω.

γι αυτο κανετε ετσι? αυτο το εχω αποδειξει στην τριτη γυμνασιου οταν καναμε τα πολυωνυμα. Αλλα τελικα δεν εβγαινε ετσι η ασκηση και την πεταξα... κριμα. η ευκαιρια χαθηκε, μια για παντα

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Γιώργος]

γι αυτο κανετε ετσι? αυτο το εχω αποδειξει στην τριτη γυμνασιου οταν καναμε τα πολυωνυμα. Αλλα τελικα δεν εβγαινε ετσι η ασκηση και την πεταξα... κριμα. η ευκαιρια χαθηκε, μια για παντα

Κρίμα, έχασες και το $1,000,000 που ήταν η ανταμοιβή του Clay Mathematics Institute.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[antwwwnis]

Κρίμα, έχασες και το $1,000,000 που ήταν η ανταμοιβή του Clay Mathematics Institute.

φετος στην β λυκειου θα κανουμε παλι πολυωνυμα.. εχουμε ακομα ελπιδες

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.