forum.math.uoa.gr

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

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




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 7 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: P vs NP
ΔημοσίευσηΔημοσιεύτηκε: 10 Αύγ 2010, 00:04 
Χωρίς σύνδεση

Εγγραφή: 11 Σεπ 2009, 13:16
Δημοσ.: 59
Έγινε μια αρκετά σοβαρή και αξιόλογη προσπάθεια για τη λύση του προβλήματος!
Ο Vinay Deolalikar "απέδειξε" οτι P!=NP

http://science.slashdot.org/story/10/08 ... That-P--NP

Εκεί έχει και link για τυχόν τολμηρούς που θέλουν να διαβάσουν το paper.

Ενδιαφέρον θα έχει να είναι σωστή η απόδειξη...Ο Scott Aaronson πάντως δεν φαίνεται να το πιστεύει μιας και θα δώσει $200.000 (!!!) αν η απόδειξη είναι όντως σωστή!


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: P vs NP
ΔημοσίευσηΔημοσιεύτηκε: 13 Αύγ 2010, 10:42 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 20 Οκτ 2006, 18:35
Δημοσ.: 1723
Τοποθεσια: Αθήνα
Ενδιαφέρον. Βλέπω πως τον έχουν πάρει σοβαρά τον τύπο, άρα δεν είναι μία ακόμα από τις εκατοντάδες αποδείξεις που βρωμάνε από μακριά λάθος.
Θα είναι πολύ ενδιαφέρον να δούμε να λύνεται κάτι τόσο μεγάλο. Εγώ προσωπικά δεν πίστευα πως θα το έβλεπα σύντομα.
Περιμένουμε με αγωνία...

Κάποιος καθηγητής να διαβάσει την απόδειξη?? :PP λογικά σε μερικές μέρες θα ξέρουμε αν είναι οκ.

_________________
Welcome to Stockholm


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: P vs NP
ΔημοσίευσηΔημοσιεύτηκε: 13 Αύγ 2010, 10:50 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 01 Ιουν 2008, 21:18
Δημοσ.: 1160
Τοποθεσια: Αθήνα
Tao έγραψε:
I think there are several levels to the basic question “Is the proof correct?”:

1. Does Deolalikar’s proof, after only minor changes, give a proof that P != NP?

2. Does Deolalikar’s proof, after major changes, give a proof that P != NP?

3. Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?

After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No” (as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added”. But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days).


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: P vs NP
ΔημοσίευσηΔημοσιεύτηκε: 15 Αύγ 2010, 13:50 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 18 Μαρ 2006, 00:26
Δημοσ.: 302
Τοποθεσια: Κερατσίνι
Χλωμή την κόβω την απόδειξη σύμφωνα με τα γραφόμενα :
http://scottaaronson.com/blog/?p=456

_________________
Ζήσε τα μαθηματικά σου!


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: P vs NP
ΔημοσίευσηΔημοσιεύτηκε: 15 Αύγ 2010, 15:46 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 29 Αύγ 2009, 13:32
Δημοσ.: 104
Γύρω απο το θέμα:
--- http://michaelnielsen.org/polymath1/ind ... 3DNP_paper
και το ενεργό προς το παρόν thread
--- http://rjlipton.wordpress.com/2010/08/1 ... ars-proof/


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: P vs NP
ΔημοσίευσηΔημοσιεύτηκε: 15 Αύγ 2010, 15:56 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 20 Οκτ 2006, 18:35
Δημοσ.: 1723
Τοποθεσια: Αθήνα
Το κρατούμενο είναι πως ακόμα και λάθος να είναι (που φαίνεται πως είναι), είναι ένα άρθρο που κάνει κάποια πρόοδο και εισάγει κάποιες νέες ιδέες.

_________________
Welcome to Stockholm


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: P vs NP
ΔημοσίευσηΔημοσιεύτηκε: 16 Αύγ 2010, 12:07 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 18 Μαρ 2006, 00:26
Δημοσ.: 302
Τοποθεσια: Κερατσίνι
http://rjlipton.wordpress.com/2010/08/1 ... ars-proof=

συζήτηση για κενά στην απόδειξη...

_________________
Ζήσε τα μαθηματικά σου!


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

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


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

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


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

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