forum.math.uoa.gr
http://forum.math.uoa.gr/

Είναι το P=NP?
http://forum.math.uoa.gr/viewtopic.php?f=94&t=2109
Σελίδα 1 από 1

Συγγραφέας:  Khelben [ 12 Σεπ 2007, 20:37 ]
Θέμα δημοσίευσης:  Είναι το P=NP?

Ένα από τα μεγαλύτερα ερωτήματα της Θεωρητικής Πληροφορικής και κατα την γνώμη μου των σύγχρονων μαθηματικών είναι το P=NP....

Είναι πραγματικά απελπιστικό το πόσο λίγο χαίρουν εκτίμησης τα συγκεκριμένα μαθηματικά από την μαθηματική κοινότητα του Πανεπιστημίου Αθηνών!!!!
(Ακόμα και την θεωρία γραφημάτων κάποιοι την θεωρούν "ζωγραφιές",ασχέτως αν οι μέθοδοί της έρχονται από την συνδυαστική την καθαρότερη μορφή μαθηματικών αν δεν κάνω λάθος...)

Μπορεί,λόγω ΜΠΛΑ,να χαρακτηριστώ μεροληπτικός αλλά πραγματικά όποιος έχει ακούσει έστω και "ξώφαλτσα" το εν λόγω ερώτημα θα του πρότεινα να ασχοληθεί...

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

Συγγραφέας:  kamenos [ 13 Σεπ 2007, 00:25 ]
Θέμα δημοσίευσης: 

Αυτο δεν ειναι ενα απο τα Clay Institute Problems;;

Συγγραφέας:  jsimos [ 13 Σεπ 2007, 15:32 ]
Θέμα δημοσίευσης: 

Ωραιο τοπικ..φανταζομαι οτι το ανοιξες για να γινει λιγο συζητηση..και οχι να βρεθει η αποδειξη :lol:


Παντως, ειναι εκπληκτικο το ποσο λιγο προοδο εχει κανει η θεωρητικη πληροφορικη μεχρι σημερα..αν σκεφτει κανεις τι επικρατει στην αντιπερα οχθη. :)


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

Οποια και να ειναι η απαντηση..στο ερωτημα που ελπιζουμε να υπαρχει απαντηση βασικα..το σιγουρο ειναι οτι θα προκειται για ενα πολυ μεγαλο βημα στον χωρο.

Συγγραφέας:  Khelben [ 13 Σεπ 2007, 16:47 ]
Θέμα δημοσίευσης: 

Ναί,το συγκεκριμένο πρόβλημα είναι στην λίστα του Clay (οπότε ας στρωθούμε... :P )

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

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

Μερικές άλλες μέθοδοι είναι οι εξής:

1.Λογικά κυκλώματα(όπου μεταφέρουμε την δυσκολία σε πολυπλοκότητα χώρου που υποτίθεται "κατανοούμε" καλύτερα)

2.Με λογική,έχουν γίνει προσπάθειες να δειχθεί ότι τελικά δεν αποδεικνύεται ούτε το P=NP ούτε το αντίθετο...

3.Με Αλγεβρική Γεωμετρία,όσο και να μην το πιστεύει κανείς υπάρχει κάποιος στο Chicago (Mulmuley) όπου με την λεγόμενη Γεωμετρική πολυπλοκότητα έχει φτάσει σε κάποια αποτελέσματα (P vs NC without bit operations) και συνεχίζει προς την κορυφή του παγόβουνου(P vs NP) :!: :!: :!:

Πραγματικά το ερώτημα είναι πολύ ενδιαφέρον και διατυπώνεται (εκλαικευμένα) με πολλούς τρόπους:

Μπορούν ποτέ οι μηχανές να φτάσουν να "σκέφτονται" :?:

Συγγραφέας:  jsimos [ 14 Σεπ 2007, 03:53 ]
Θέμα δημοσίευσης: 

Khelben έγραψε:

3.Με Αλγεβρική Γεωμετρία,όσο και να μην το πιστεύει κανείς υπάρχει κάποιος στο Chicago (Mulmuley) όπου με την λεγόμενη Γεωμετρική πολυπλοκότητα έχει φτάσει σε κάποια αποτελέσματα (P vs NC without bit operations) και συνεχίζει προς την κορυφή του παγόβουνου(P vs NP) :!: :!: :!:

Πραγματικά το ερώτημα είναι πολύ ενδιαφέρον και διατυπώνεται (εκλαικευμένα) με πολλούς τρόπους:

Μπορούν ποτέ οι μηχανές να φτάσουν να "σκέφτονται" :?:


Δεν το ηξερα για αυτη την προσεγγιση. :) Mπορεις να ποσταρεις καποιο σχετικο link? ή καποιο paper? Mε Αλγεβρικη γεωμετρια θα ειναι πολυ ενδιαφερον.


Τωρα για το ερωτημα σου..προσωπικη μου αποψη..οχι. Παντα θα χρειαζεται καποιος να δωσει το input. ;)[/i]

Συγγραφέας:  Khelben [ 14 Σεπ 2007, 11:56 ]
Θέμα δημοσίευσης: 

Το link με καμια 10αρια σχετικά paper είναι το εξής:

http://ramakrishnadas.cs.uchicago.edu/

Πάντως οι εργασίες του συγκεκριμένου κάνουν 3-4 χρόνια να δημοσιευτούν γιατί είναι ο μόνος που καταλαβαίνει τι κάνει(και προφανώς δεν κάνει βλακείες!!!)

Σελίδα 1 από 1 Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/