forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 21 Νοέμ 2017, 04:37

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 6 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Είναι το P=NP?
ΔημοσίευσηΔημοσιεύτηκε: 12 Σεπ 2007, 20:37 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφή: 20 Αύγ 2006, 20:56
Δημοσ.: 51
Τοποθεσια: Myth Drannor(Waterdeep)
Ένα από τα μεγαλύτερα ερωτήματα της Θεωρητικής Πληροφορικής και κατα την γνώμη μου των σύγχρονων μαθηματικών είναι το P=NP....

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

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

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


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 13 Σεπ 2007, 00:25 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 15 Μαρ 2007, 12:37
Δημοσ.: 2388
Αυτο δεν ειναι ενα απο τα Clay Institute Problems;;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 13 Σεπ 2007, 15:32 
Χωρίς σύνδεση
S.F.I. Director
Άβαταρ μέλους

Εγγραφή: 01 Μαρ 2006, 14:57
Δημοσ.: 227
Τοποθεσια: echo "$HOST"
Ωραιο τοπικ..φανταζομαι οτι το ανοιξες για να γινει λιγο συζητηση..και οχι να βρεθει η αποδειξη :lol:


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


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

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

_________________
Εικόνα

Eirik loves windows...[is true]

kill -9 2006...


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 13 Σεπ 2007, 16:47 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφή: 20 Αύγ 2006, 20:56
Δημοσ.: 51
Τοποθεσια: Myth Drannor(Waterdeep)
Ναί,το συγκεκριμένο πρόβλημα είναι στην λίστα του Clay (οπότε ας στρωθούμε... :P )

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

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

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

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

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

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

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

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


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 14 Σεπ 2007, 03:53 
Χωρίς σύνδεση
S.F.I. Director
Άβαταρ μέλους

Εγγραφή: 01 Μαρ 2006, 14:57
Δημοσ.: 227
Τοποθεσια: echo "$HOST"
Khelben έγραψε:

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

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

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


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


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

_________________
Εικόνα

Eirik loves windows...[is true]

kill -9 2006...


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: 14 Σεπ 2007, 11:56 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφή: 20 Αύγ 2006, 20:56
Δημοσ.: 51
Τοποθεσια: Myth Drannor(Waterdeep)
Το link με καμια 10αρια σχετικά paper είναι το εξής:

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

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


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 6 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group