Λύθηκε το "P=NP?" ;

THMMY.gr > Forum > Χαλαρή συζήτηση - κουβεντούλα > Φιλόσοφοι Μηχανικοί - Μηχανικοί Φιλόσοφοι > Επιστήμες (Moderators: Mr Watson, Tasos Bot) > Λύθηκε το "P=NP?" ;

0 Members and 1 Guest are viewing this topic.

Pages: [1]

Author

Topic: Λύθηκε το "P=NP?" ; (Read 2101 times)

Junior

Μόνιμος κάτοικος ΤΗΜΜΥ.gr

Gender:

Posts: 1349

Λύθηκε το "P=NP?" ;

« on: August 17, 2010, 15:56:38 pm »

Ένας Ινδός επιστήμονας δημοσίευσε μια απόδειξη ότι P διάφορο του NP.
Αυτή τη στιγμή ελέγχεται αν είναι σωστή η λύση του. Αν είναι όντως σωστή, θα έχει κερδίσει ένα εκατομμύριο δολάρια από το ινστιτούτο Clay!

Άρθρο της Ελευθεροτυπίας:
http://www.enet.gr/?i=news.el.episthmh-texnologia&id=192213

Άρθρο σε ξένο site:
http://www.livemint.com/2010/08/10230113/Indian-scientist-offers-proof.html?h=E

Το ίδιο το paper που δημοσιεύτηκε:
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

Το πρόβλημα αυτό είναι το πιο γνωστό πρόβλημα στη θεωρία των αλγορίθμων. Με P συμβολίζονται όλα τα προβλήματα που κατά κάποιο τρόπο μπορούν να λυθούν σε λογικό χρόνο (ανεξαρτήτως της μηχανής που χρησιμοποιούμε). Με NP συμβολίζονται τα προβλήματα που, δεδομένης μιας λύσης, μπορεί αυτή να επαληθευτεί σε λογικό χρόνο.
Για παράδειγμα, το να λύσουμε ένα Sudoku φαίνεται πολύ πιο δύσκολο από το να ελέγξουμε μια λύση αν είναι σωστή.

Ένα ερώτημα που απασχολεί πολύ τους θεωρητικούς των υπολογιστών και του οποίου η απάντηση (θετική ή αρνητική) θα έχει μεγάλες συνέπειες στην επιστήμη των υπολογιστών, είναι το αν υπάρχουν προβλήματα που ελέγχονται σε "λογικό" χρόνο, αλλά δεν μπορούν να λυθούν σε "λογικό" χρόνο, δηλαδή αν υπάρχουν προβλήματα στην κλάση NP που δεν ανήκουν στην κλάση P. Ή αλλιώς το ερώτημα "P=NP?"


	Logged

Nessa NetMonster

Καταστραμμένος

Posts: 7044

Ιούνιος 1999 - 19/7/2009

Re: Λύθηκε το "P=NP?" ;

« Reply #1 on: August 17, 2010, 16:41:13 pm »

Το άρθρο της Ελευθεροτυπίας είναι γτπ...


	Logged

Διεθνιστική Εργατική Αριστερά
Διεθνιστική Αριστερά
Εργατική Αριστερά

RedNet Θεσσαλονίκης

png

Veteran
Μόνιμος κάτοικος ΤΗΜΜΥ.gr

Gender:

Posts: 2101

Re: Λύθηκε το "P=NP?" ;

« Reply #2 on: August 17, 2010, 17:46:07 pm »

Αν θυμάμαι καλά, ο Ντελόπουλος στα συστήματα υπολογιστών μας είχε αναφέρει την εικασία "P υποσύνολο ή ίδιο του ΝΡ".

Αν ο ινδός είναι σωστός, από του χρόνου θέλει update Tongue


	Logged

τακτοποιημένο χάος

^^DaRk_HunTeR

Μόνιμος κάτοικος ΤΗΜΜΥ.gr

Gender:

Posts: 2149

0001 0010 0100 0010

Re: Λύθηκε το "P=NP?" ;

« Reply #3 on: August 17, 2010, 18:03:31 pm »

Αντιγραφω

Quote

"Dear Fellow Researchers,

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.

http://www.scribd.com/doc/35539144/pnp12pt

The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.

This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.

This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.

Comments and suggestions for improvements to the paper are highly welcomed."

http://feedworld.net/toc/

http://www.claymath.org/millennium/P_vs_NP/

Απο μειλ του Νικου στη λιστα στις 8/8/2010


	Logged

Without order nothing can exist without chaos nothing can evolve

Timeo hominem unius libri
The minstrel

Μάρω

Guest

Re: Λύθηκε το "P=NP?" ;

« Reply #4 on: August 17, 2010, 19:05:12 pm »

Quote from: png on August 17, 2010, 17:46:07 pm

ναι, το λέει κ στις σημειώσεις Cheesy


	Logged

Joseph D.

Μόνιμος κάτοικος ΤΗΜΜΥ.gr

Gender:

Posts: 1082

Someone else might have gotten it wrong.

Re: Λύθηκε το "P=NP?" ;

« Reply #5 on: August 17, 2010, 21:24:50 pm »

Μήπως ο Ινδός είναι ο David Krumholtz; Tongue


	Logged

'No tests on species with members capable of calculus. Simple rule, never broke it.'

Pages: [1]

Jump to: