Επτά Προκλήσεις της Χιλιετίας
Πρότυπο 1 Το πρόβλημα του μάγειρα (διατυπώθηκε το 1971)
Ας υποθέσουμε ότι, όντας σε μια μεγάλη εταιρεία, θέλετε να βεβαιωθείτε ότι ο φίλος σας είναι επίσης εκεί. Αν σας πουν ότι κάθεται στη γωνία, τότε αρκεί ένα κλάσμα του δευτερολέπτου για να βεβαιωθείτε με μια ματιά ότι οι πληροφορίες είναι αληθινές. Ελλείψει αυτών των πληροφοριών, θα αναγκαστείτε να περιηγηθείτε σε ολόκληρο το δωμάτιο, κοιτάζοντας τους καλεσμένους. Αυτό υποδηλώνει ότι η επίλυση ενός προβλήματος απαιτεί συχνά περισσότερο χρόνο από τον έλεγχο της ορθότητας της λύσης.
Ο Stephen Cook διατύπωσε το πρόβλημα: μπορεί ο έλεγχος της ορθότητας μιας λύσης σε ένα πρόβλημα να είναι μεγαλύτερος από τη λήψη της ίδιας της λύσης, ανεξάρτητα από τον αλγόριθμο επαλήθευσης. Αυτό το πρόβλημα είναι ένα από τα άλυτα προβλήματα της λογικής και της επιστήμης των υπολογιστών. Η λύση του θα μπορούσε να φέρει επανάσταση στις βασικές αρχές της κρυπτογραφίας που χρησιμοποιείται στη μετάδοση και αποθήκευση δεδομένων.
2. Η υπόθεση Riemann (διατυπώθηκε το 1859)
Μερικοί ακέραιοι αριθμοί δεν μπορούν να εκφραστούν ως το γινόμενο δύο μικρότερων ακεραίων, όπως 2, 3, 5, 7 κ.λπ. Αυτοί οι αριθμοί ονομάζονται πρώτοι αριθμοί και παίζουν σημαντικό ρόλο στα καθαρά μαθηματικά και τις εφαρμογές τους. Η κατανομή των πρώτων αριθμών μεταξύ όλων των φυσικών αριθμών δεν ακολουθεί καμία κανονικότητα. Ωστόσο, ο Γερμανός μαθηματικός Riemann έκανε μια υπόθεση σχετικά με τις ιδιότητες μιας ακολουθίας πρώτων αριθμών. Εάν αποδειχθεί η υπόθεση Riemann, θα φέρει επανάσταση στις γνώσεις μας για την κρυπτογράφηση και θα οδηγήσει σε πρωτοφανείς ανακαλύψεις στην ασφάλεια του Διαδικτύου.
3. Υπόθεση Birch και Swinnerton-Dyer (διατυπώθηκε το 1960)
Συνδέεται με την περιγραφή του συνόλου των λύσεων ορισμένων αλγεβρικών εξισώσεων σε πολλές μεταβλητές με ακέραιους συντελεστές. Παράδειγμα αλγεβρικής εξίσωσης είναι η εξίσωση x2 + y2 = z2. Ο Ευκλείδης έδωσε μια πλήρη περιγραφή των λύσεων αυτής της εξίσωσης, αλλά για πιο σύνθετες εξισώσεις, η απόκτηση μιας λύσης γίνεται εξαιρετικά δύσκολη.
4. Υπόθεση Hodge (διατυπώθηκε το 1941)
Τον 20ο αιώνα, οι μαθηματικοί ανακάλυψαν μια ισχυρή μέθοδο για τη μελέτη του σχήματος σύνθετων αντικειμένων. Η κύρια ιδέα είναι να χρησιμοποιήσετε απλά «τούβλα» αντί για το ίδιο το αντικείμενο, τα οποία είναι κολλημένα μεταξύ τους και σχηματίζουν την ομοιότητά του. Η υπόθεση Hodge συνδέεται με ορισμένες υποθέσεις σχετικά με τις ιδιότητες τέτοιων «τούβλων» και αντικειμένων.
5. Οι εξισώσεις Navier-Stokes (διατυπώθηκαν το 1822)
Εάν πλεύσετε με μια βάρκα στη λίμνη, τότε θα προκύψουν κύματα και εάν πετάξετε με αεροπλάνο, θα προκύψουν ταραχώδη ρεύματα στον αέρα. Υποτίθεται ότι αυτά και άλλα φαινόμενα περιγράφονται με εξισώσεις γνωστές ως εξισώσεις Navier-Stokes. Οι λύσεις αυτών των εξισώσεων είναι άγνωστες και δεν είναι καν γνωστός ο τρόπος επίλυσής τους. Είναι απαραίτητο να δείξουμε ότι η λύση υπάρχει και είναι μια αρκετά ομαλή λειτουργία. Η λύση αυτού του προβλήματος θα καταστήσει δυνατή τη σημαντική αλλαγή των μεθόδων διεξαγωγής υδρο- και αεροδυναμικών υπολογισμών.
6. Πρόβλημα Poincare (διατυπώθηκε το 1904)
Εάν τεντώσετε ένα λάστιχο πάνω από ένα μήλο, τότε μπορείτε να μετακινήσετε αργά την ταινία χωρίς να αφήσετε την επιφάνεια, να τη συμπιέσετε σε ένα σημείο. Από την άλλη πλευρά, εάν το ίδιο λαστιχάκι τεντωθεί σωστά γύρω από το ντόνατ, δεν υπάρχει τρόπος να συμπιεστεί η ταινία σε ένα σημείο χωρίς να σκιστεί η ταινία ή να σπάσει το ντόνατ. Η επιφάνεια ενός μήλου λέγεται ότι είναι απλά συνδεδεμένη, αλλά η επιφάνεια ενός ντόνατ δεν είναι. Αποδείχθηκε ότι ήταν τόσο δύσκολο να αποδειχθεί ότι μόνο η σφαίρα είναι απλά συνδεδεμένη που οι μαθηματικοί εξακολουθούν να αναζητούν μια απάντηση.
7. Εξισώσεις Yang-Mills (διατυπώθηκαν το 1954)
Οι εξισώσεις της κβαντικής φυσικής περιγράφουν τον κόσμο των στοιχειωδών σωματιδίων. Οι φυσικοί Yang και Mills, έχοντας ανακαλύψει τη σύνδεση μεταξύ γεωμετρίας και φυσικής στοιχειωδών σωματιδίων, έγραψαν τις δικές τους εξισώσεις. Έτσι, βρήκαν έναν τρόπο να ενοποιήσουν τις θεωρίες ηλεκτρομαγνητικών, αδύναμων και ισχυρών αλληλεπιδράσεων. Οι εξισώσεις Yang-Mills υπονοούσαν την ύπαρξη σωματιδίων που πράγματι παρατηρήθηκαν σε εργαστήρια σε όλο τον κόσμο, έτσι η θεωρία Yang-Mills γίνεται αποδεκτή από τους περισσότερους φυσικούς, παρά το γεγονός ότι αυτή η θεωρία εξακολουθεί να αποτυγχάνει να προβλέψει τις μάζες των στοιχειωδών σωματιδίων.
|
Τελευταία ενημέρωση: 05/10/2019 02:40 +0300
  
|
Η τιμή να είναι το "πρώτο" πλήρες πρόβλημα NP έπεσε στο πρόβλημα αναγνώρισης από τη λογική Boole, ένα πρόβλημα που συνήθως αναφέρεται ως SATIBILITY (συντομογραφία SP). Οι όροι που χρησιμοποιούνται για την περιγραφή του ορίζονται ως εξής.
Έστω U = (u 1 , u 2 , ..., u m ) το σύνολο των Boolean μεταβλητών. Με ένα σύνολο τιμών αλήθειας σε ένα σύνολο U εννοούμε μια συνάρτηση t: U→(T, F). Αν t(u)=T, τότε θα πούμε ότι το u είναι "αληθές" σε σχέση με το t. αν t(u) = F, τότε λέμε ότι το u παίρνει την τιμή "false". Αν το u είναι μια μεταβλητή από το U, τότε το u και και λέγονται κυριολεκτικά από το U. Το literal and είναι αληθές ως προς το t εάν και μόνο αν η μεταβλητή και είναι αληθές ως προς το t. κυριολεκτική και αξιολογείται σε αληθές εάν και μόνο εάν η μεταβλητή αξιολογείται ως "false".
Ένας διαχωρισμός πάνω από το U είναι ένα σύνολο κυριολεκτικών πάνω από το U, για παράδειγμα (u 1 , u 3 , u 8 ). Αντιπροσωπεύει τον διαχωρισμό αυτών των κυριολεκτικών και λέγεται ότι ικανοποιείται για κάποιο σύνολο τιμών αλήθειας, εάν και μόνο εάν, για το σύνολο των τιμών αλήθειας που εξετάζουμε, τουλάχιστον ένα από τα μέλη του λάβει την τιμή "αληθής". Στο παράδειγμά μας, η διάζευξη θα εκτελεστεί σε σχέση με το t εάν δεν αποδειχθεί ταυτόχρονα ότι t(u 1) = F, t(u 3) = T, t(u 8) = F. Ένα σύνολο C αποσυνδέσεων πάνω από το U ονομάζεται ικανοποιητικό εάν και μόνο στην περίπτωση που υπάρχει κάποιο σύνολο τιμών αλήθειας στο σύνολο U έτσι ώστε όλες οι αποσυνδέσεις από το C να ικανοποιούνται ταυτόχρονα. Ένα τέτοιο σύνολο τιμών αλήθειας ονομάζεται ικανοποιητικό σύνολο αλήθειας τιμές για το C. Το πρόβλημα ΑΣΦΑΛΕΙΑΣ διατυπώνεται ως εξής:
ΣΚΟΠΙΜΟΤΗΤΑ
ΚΑΤΑΣΤΑΣΗ. Δίνεται ένα σύνολο μεταβλητών U και ένα σύνολο C από διαχωρισμούς έναντι του U.
ΕΡΩΤΗΣΗ. Υπάρχει ένα ικανοποιητικό σύνολο τιμών αλήθειας για το C;
Για παράδειγμα, έστω U = (u 1 , u 2 ) και C= ((u 1 , u 2 ), (u 1 , u 2 )). Αυτή είναι μια μεμονωμένη εργασία από τη διεπαφή χρήστη, η απάντηση στην οποία είναι "ναι". Η εργασία των τιμών αλήθειας ορίζεται ως εξής: t (u 1) \u003d t (u 2) \u003d T. Από την άλλη πλευρά, αντικαθιστώντας το C με C "= ((u 1, u 2), (u 1, u 2), (u 1)), παίρνουμε ένα παράδειγμα μεμονωμένης εργασίας, η απάντηση στην οποία είναι "όχι", αφού το C είναι αδύνατη. Μπορούμε τώρα να διατυπώσουμε το θεμελιώδες θεώρημα του Κουκ.
Θεώρημα 2.2 (θεώρημα του Κουκ). Υπάρχει ένα έργο σκοπιμότηταςNP- ολοκληρωμένη εργασία.
Απόδειξη. Είναι εύκολο να δούμε ότι το PRI βρίσκεται στην κατηγορία NP. Για να το λύσει ένας μη ντετερμινιστικός αλγόριθμος, αρκεί να καθορίσετε ένα σύνολο τιμών αλήθειας στο αρχικό σύνολο μεταβλητών και να ελέγξετε ότι αυτό το σύνολο τιμών πληροί όλες τις αποσυνδέσεις από το αρχικό σύνολο C. Όλα αυτά είναι εύκολα να κάνουμε (με μη ντετερμινιστικό τρόπο) σε πολυωνυμικό χρόνο. Έτσι, πληρούται η πρώτη απαίτηση που πρέπει να ικανοποιούν τα προβλήματα NP-complete.
Για να επαληθεύσουμε την εκπλήρωση της δεύτερης απαίτησης, ας επιστρέψουμε στο επίπεδο των γλωσσών, δηλαδή στην αναπαράσταση του SP με τη γλώσσα Lvp = L[vyp, e] για κάποιο εύλογο σχήμα κωδικοποίησης ε. Είναι απαραίτητο να Δείξτε ότι για όλες τις γλώσσες L e NP, η σχέση L ∞ Lout. Οι διαφορετικές γλώσσες από το NP μπορεί να είναι πολύ διαφορετικές. ο αριθμός αυτών των γλωσσών είναι άπειρος, επομένως δεν είναι δυνατό να καθοριστεί ξεχωριστή σημείωση για καθεμία από αυτές. Ωστόσο, κάθε γλώσσα στο NP μπορεί να αναπαρασταθεί σε μια τυπική μορφή, δηλαδή, από ένα πρόγραμμα NDMT πολυωνυμικού χρόνου που αναγνωρίζει αυτή τη γλώσσα.
Μια τέτοια αναπαράσταση καθιστά δυνατή την αντιμετώπιση ενός γενικού προγράμματος NDMT του οποίου ο χρόνος εκτέλεσης είναι πολυωνυμικός και η απόκτηση της γενικής αναγωγιμότητας της γλώσσας που αναγνωρίζεται από αυτό το πρόγραμμα σε Lout σε Lvy. Έτσι, στην ουσία, για όλα τα L ε NP, θα παρουσιαστεί μια γενική απόδειξη ότι L ∞ Lvy.
Αρχικά, θεωρήστε ένα αυθαίρετο πρόγραμμα NDMT M με πολυωνυμικό χρόνο εκτέλεσης, το οποίο έχει συνιστώσες Г, Σ, b, Q, q 0 , q y , q n , δ και αναγνωρίζει τη γλώσσα L = L M . Επιπλέον, έστω p(n) ένα πολυώνυμο με ακέραιους συντελεστές που οριοθετεί τη χρονική πολυπλοκότητα T m (n) από πάνω. (Χωρίς απώλεια γενικότητας, μπορούμε να υποθέσουμε ότι p(n) ≥ n για όλα τα n ε Z+.) Η συνάρτηση f L , η οποία υλοποιεί τη γενική αναγωγιμότητα, θα περιγραφεί με όρους M, G, Σ, b, Q, q 0 , q Y , q n , δ και р.
Είναι βολικό να σκεφτούμε το f L ως μια αντιστοίχιση από το σύνολο των λέξεων στο αλφάβητο 2 στα μεμονωμένα προβλήματα στο UT, παρά στις λέξεις του αλφαβήτου S που κωδικοποιούν τις εργασίες σε LT, καθώς οι λεπτομέρειες κωδικοποίησης μπορούν να ολοκληρωθούν εύκολα. Έτσι, η συνάρτηση f l θα έχει την ιδιότητα ότι για όλα τα x ε Σ* η ιδιότητα μέλους x ε L λαμβάνει χώρα εάν και μόνο εάν το σύνολο των διαχωρισμών f l (x) έχει ένα ικανοποιητικό σύνολο τιμών αλήθειας. Το κλειδί για την κατασκευή της συνάρτησης f L είναι η χρήση κάποιου συνόλου διαχωρισμών για να γράψετε τη δήλωση ότι το x είναι αποδεκτό από το πρόγραμμα NDMT M, δηλαδή η πρόταση x ε L.
Εάν η λέξη εισόδου x ε Σ* λαμβάνεται από το πρόγραμμα M, τότε για το x υπάρχει αξιολόγηση λήψης του προγράμματος M έτσι ώστε ο αριθμός των βημάτων στο στάδιο δοκιμής και ο αριθμός των χαρακτήρων στη λέξη εικασίας περιορίζονται σε p (n), όπου n = |x|. Μόνο κελιά με αριθμούς από -p(n) έως p(n)+1 θα συμμετέχουν σε έναν τέτοιο υπολογισμό. Αυτό προκύπτει από το γεγονός ότι η κεφαλή ανάγνωσης/εγγραφής ξεκινά από το κελί αριθμό 1 και μετακινείται το πολύ 1 κελί σε κάθε βήμα. Ο υπολογισμός ελέγχου καθορίζεται πλήρως ρυθμίζοντας σε κάθε χρονική στιγμή τα περιεχόμενα των κελιών με τους υποδεικνυόμενους αριθμούς, την εσωτερική κατάσταση και τη θέση της κεφαλής ανάγνωσης/εγγραφής. Επιπλέον, δεδομένου ότι υπάρχουν το πολύ p(n) βήματα στον υπολογισμό ελέγχου, πρέπει να ληφθούν υπόψη το πολύ p(n) + 1 χρονικά σημεία. Αυτό καθιστά δυνατή την πλήρη περιγραφή ενός τέτοιου υπολογισμού χρησιμοποιώντας έναν πολυωνυμικά περιορισμένο αριθμό μεταβλητών Boolean και κάποιο σύνολο τιμών αλήθειας στο σύνολο τους.
Το σύνολο των μεταβλητών U που εμπλέκονται στην περιγραφή της συνάρτησης f L προορίζεται για τους καθορισμένους σκοπούς. Επαναριθμούμε τα στοιχεία των συνόλων Q και Г ως εξής: Q: q 0 , q 1 = q y , q 2 = q N , q s , ..., q r , όπου r = |Q|; Г: s 0 = b, s 1 s 2 , ..., s v , όπου v=|Г| - 1. Τρεις τύποι μεταβλητών θα συμμετάσχουν σε περαιτέρω συλλογισμό, καθένας από τους οποίους έχει ορισμένο νόημα σύμφωνα με το Σχ. 2.7. Σε αυτή την περίπτωση, η φράση "in time i" είναι συντομογραφία της ακριβούς έκφρασης "μετά την εκτέλεση του βήματος j-ro του υπολογισμού επαλήθευσης".
Ο υπολογισμός του προγράμματος M προκαλεί προφανώς ένα σύνολο τιμών αλήθειας στο σύνολο αυτών των μεταβλητών, εάν δεχθούμε τη συμφωνία ότι όταν ο υπολογισμός τελειώνει πριν από την ώρα p(n), η διαμόρφωση παραμένει αμετάβλητη ανά πάσα στιγμή μετά τη διακοπή , δηλαδή η τελική κατάσταση, η θέση του κεφαλιού και η εγγραφή κασέτας. Τη χρονική στιγμή μηδέν, η εγγραφή κασέτας αποτελείται από τη λέξη εισόδου x που βρίσκεται σε κελιά με αρίθμηση από το 1 έως το n και τη λέξη εικασίας w στα κελιά με αριθμό από -1 έως |w|, ενώ όλα τα άλλα κελιά είναι άδεια.
Από την άλλη πλευρά, ένα αυθαίρετο σύνολο τιμών αλήθειας για αυτές τις μεταβλητές δεν αντιστοιχεί απαραίτητα σε κάποιο είδος υπολογισμού, πολύ λιγότερο σε έναν αποδεκτό. Με ένα αυθαίρετο σύνολο τιμών αλήθειας για μεταβλητές σε κάποιο κελί, θα μπορούσαμε
ρύζι. 2.7. Μεταβλητές συνόλου διαχωρισμούfl(Χ) και το νόημα που τους αποδίδεται
αρκετοί διαφορετικοί χαρακτήρες θα μπορούσαν να γραφτούν ταυτόχρονα, το μηχάνημα θα μπορούσε να βρίσκεται σε πολλές διαφορετικές καταστάσεις ταυτόχρονα και η κεφαλή ανάγνωσης/εγγραφής μπορούσε ταυτόχρονα να σαρώσει οποιοδήποτε υποσύνολο κελιών αριθμημένο από -p(n) έως p(n)+ 1. Η περιγραφή της συνάρτησης f L πραγματοποιείται με την κατασκευή ενός τέτοιου συνόλου διαχωρισμών που περιέχει τις απαριθμημένες μεταβλητές που το σύνολο των τιμών αλήθειας θα είναι ικανοποιητικό εάν και μόνο εάν αυτό το σύνολο τιμών αλήθειας επάγεται από κάποιον υπολογισμό λήψης στο η είσοδος x και το στάδιο επαλήθευσης αυτού του υπολογισμού δεν παίρνει περισσότερα από p (n) βήματα και η λέξη εικασίας έχει μήκος το πολύ p(n). Έτσι παίρνουμε τις συνέπειες:
x ε L ↔ στην είσοδο x υπάρχει ένας αποδεκτός υπολογισμός του προγράμματος M
↔ Στην είσοδο x, υπάρχει μια αποδεκτή αξιολόγηση του προγράμματος M, ο αριθμός των βημάτων του οποίου δεν υπερβαίνει το p(n) και η εικαστική λέξη w έχει μήκος ίσο με p(n).
↔ Υπάρχει ένα σύνολο τιμών αλήθειας για το σύνολο των διαχωρισμών του προβλήματος f l (x).
Αυτό θα σημαίνει ότι η f l ικανοποιεί μία από τις δύο προϋποθέσεις που απαιτούνται στον ορισμό της πολυωνυμικής αναγωγιμότητας. Μια άλλη προϋπόθεση, η οποία είναι ότι το fl πρέπει να είναι υπολογίσιμο σε πολυωνυμικό χρόνο, μπορεί να ελεγχθεί εύκολα μετά την περιγραφή του f l . θα τελειώσει.
Οι διαχωρισμοί του επιμέρους προβλήματος f i (x) μπορούν να υποδιαιρεθούν σε 6 ομάδες, καθεμία από τις οποίες θα επιβάλλει έναν ορισμένο τύπο περιορισμού σε οποιοδήποτε ικανοποιητικό σύνολο τιμών αλήθειας. Αυτές οι ομάδες φαίνονται στο Σχ. 2.8.
Ρύζι. 2.8.Ομάδες διαχωρισμού γιαφά μεγάλο (x) και τους περιορισμούς που επιβάλλουν στο ικανοποιητικό σύνολο των τιμών αλήθειας.
Είναι εύκολο να διαπιστωθεί ότι εάν και οι 6 ομάδες διαχωρισμών επιτύχουν πραγματικά τους στόχους τους, τότε το εκπληρωμένο σύνολο τιμών αλήθειας πρέπει να αντιστοιχεί στον επιθυμητό υπολογισμό λήψης στην είσοδο x. Το μόνο που μένει είναι να υποδείξουμε έναν τρόπο κατασκευής ομάδων διαχωρισμών που επιτυγχάνουν αυτούς τους στόχους.
Η ομάδα G 1 αποτελείται από τις ακόλουθες διαχωρίσεις:
(Q, Q, .... Q(i, r]), 0 Ο πρώτος p(n)+1 από αυτούς τους διαχωρισμούς μπορεί να εκτελεστεί ταυτόχρονα εάν και μόνο εάν κάθε φορά i το πρόγραμμα M βρίσκεται σε τουλάχιστον μία κατάσταση. Οι υπόλοιπες (p(n)+1) (r + 1) (r/2) διαχωρισμοί μπορούν να εκτελεστούν ταυτόχρονα εάν και μόνο εάν σε καμία στιγμή i το πρόγραμμα M δεν βρίσκεται σε περισσότερες από μία καταστάσεις. Έτσι, το G1 εκπληρώνει τον σκοπό του. Οι ομάδες G 2 και G 3 κατασκευάζονται παρόμοια, αλλά οι ομάδες G 4 και G 5 είναι πολύ απλές, καθεμία από αυτές περιλαμβάνει προτάσεις που αποτελούνται μόνο από ένα κυριολεκτικό. Στο σχ. Το 2.9 δίνει μια πλήρη περιγραφή των πρώτων πέντε ομάδων διαχωρισμών. Σημειώστε ότι τόσο ο αριθμός των διαχωρισμών σε αυτές τις ομάδες όσο και ο μέγιστος αριθμός των κυριολεκτικών σε κάθε διαχωρισμό περιορίζονται από κάποιο πολυώνυμο στο n (επειδή το r και το v είναι σταθερές, οι οποίες ορίζονται από το M και, επομένως, από τη γλώσσα L). Ρύζι. 2.9.Οι πρώτες 5 ομάδες διαζυγίων για
φά
μεγάλο
(Χ).
Η περιγραφή της τελευταίας ομάδας διαχωρισμών, G 6 , φαίνεται κάπως πιο περίπλοκη, γεγονός που εγγυάται ότι κάθε επόμενη διαμόρφωση μηχανής λαμβάνεται από την προηγούμενη ως αποτέλεσμα της εφαρμογής μιας εντολής του προγράμματος M. Αυτή η ομάδα αποτελείται από δύο υποομάδες διαχωρισμών . Η πρώτη υποομάδα εγγυάται ότι εάν η κεφαλή του αναγνώστη/εγγραφής τη στιγμή i δεν κοιτάξει τον αριθμό κελιού j, τότε ο χαρακτήρας στον αριθμό κελιού j δεν θα αλλάζει από καιρό σε i + 1. Οι διαχωρισμοί αυτής της υποομάδας έχουν τη μορφή Ας καθορίσουμε αυθαίρετα έναν χρόνο t, ένα κελί με αριθμό j και σύμβολο s l Εάν τη στιγμή i η κεφαλή ανάγνωσης/εγγραφής δεν σαρώσει το κελί με αριθμό j και σε αυτό το κελί τη στιγμή i γράφεται το σύμβολο j και τη στιγμή i + 1 είναι ήδη εκεί αν όχι, τότε ο παραπάνω διαχωρισμός θα αποτύχει (αλλιώς θα αποτύχει). Έτσι, οι 2(p(n) + l) 2 (v + 1) διαχωρισμοί αυτής της ομάδας εκπληρώνουν το σκοπό τους. Η δεύτερη υποομάδα διαχωρισμών από την ομάδα G 6 εγγυάται ότι η αναδιάταξη μιας διάταξης μηχανής στην επόμενη λαμβάνει χώρα σύμφωνα με τη συνάρτηση μετάβασης δ του προγράμματος M. Για κάθε τετραπλό (i, j, k, l), 0 ≤ i< p(n),
-р(n)
≤ j
≤ р(n)
+ 1, 0 ≤ k
≤ r
и 0 ≤ l
≤ v, αυτή η υποομάδα περιέχει τις ακόλουθες τρεις ρήτρες: όπου οι τιμές Δ, k" και l" ορίζονται ως εξής: αν q k ε Q\(q y , q N ), τότε δ(q k , s l) = (q k ` , s l ` , ∆), και αν q k ε (q Y , q N ), τότε ∆= 0, k" = k και l" = l. Είναι εύκολο να δούμε (αν και αυτό μπορεί να χρειαστεί μερικά λεπτά σκέψης) ότι αυτές οι ρήτρες 6(p(n))(p(n) + 1)(r+1)(v+1) παρέχουν τον απαραίτητο περιορισμό στο ικανοποιητικό σύνολο αξιών αλήθειας. Έτσι, δείξαμε πώς να κατασκευάσουμε ομάδες διαχωρισμού G 1 - G 6 που εκπληρώνουν το σκοπό τους. Εάν x ε L, τότε το πρόγραμμα M στην είσοδο x έχει έναν αποδεκτό υπολογισμό μήκους το πολύ p(n) και αυτός ο υπολογισμός αποδίδει, δεδομένης της ερμηνείας των μεταβλητών, ένα σύνολο τιμών αλήθειας που θα ικανοποιεί όλες τις διασυνδέσεις από C=G 1 UG 2 UG 3 UG 4 UG 5 UG 6 . Αντίθετα, το σύνολο διαχωρισμού C είναι κατασκευασμένο με τέτοιο τρόπο ώστε οποιοδήποτε ικανοποιητικό σύνολο τιμών αλήθειας για το C πρέπει να αντιστοιχεί σε κάποια αξιολόγηση λήψης του προγράμματος M στην είσοδο x. Συνεπάγεται ότι για το f l (x) υπάρχει ένα ικανοποιητικό σύνολο τιμών αλήθειας αν και μόνο αν x ε L. Τώρα μένει να δείξουμε ότι, για οποιαδήποτε σταθερή γλώσσα L, ένα μεμονωμένο πρόβλημα f l (x) μπορεί να κατασκευαστεί χρονικά που περιορίζεται από ένα πολυώνυμο σε n = |x|. Εάν δοθεί η γλώσσα L, τότε μπορούμε να επιλέξουμε κάποιο πρόγραμμα NDMT M που αναγνωρίζει το L στον χρόνο που περιορίζεται από το πολυώνυμο p (δεν χρειάζεται να βρεθεί το ίδιο το μη ντετερμινιστικό πρόγραμμα σε πολυωνυμικό χρόνο, αφού είναι απαραίτητο μόνο να δείξουμε ότι το χαρτογράφηση f l υπάρχει). Δεδομένου ενός συγκεκριμένου προγράμματος NDMT M και ενός πολυωνύμου p, τότε η κατασκευή ενός συνόλου μεταβλητών U και ενός συνόλου διαχωρισμών C απαιτεί λίγη περισσότερη δουλειά από το να συμπληρώσετε όλες τις θέσεις σε έναν τυπικό (αν και μάλλον περίπλοκο) τύπο. Το πολυωνυμικό όριο αυτού του υπολογισμού θα είναι σαφές εάν δείξουμε ότι το μήκος περιορίζεται από πάνω από ένα πολυώνυμο σε n, όπου το μήκος [I], όπως υποδεικνύεται στο Sec. 2.1 χαρακτηρίζει το μήκος της λέξης που κωδικοποιεί την μεμονωμένη εργασία I, για κάποιο εύλογο σχήμα κωδικοποίησης. Ως "εύλογη" συνάρτηση μήκους για το πρόβλημα LLP, για παράδειγμα, μπορούμε να πάρουμε το |U||С|. Κανένας από τους διαχωρισμούς δεν μπορεί να περιέχει περισσότερα από 2|U| literals (επειδή ο συνολικός αριθμός των literals είναι 2|U|) και ο αριθμός των χαρακτήρων που απαιτείται για την περιγραφή κάθε μεμονωμένου κυριολεκτικού δεν είναι περισσότερος από log|U|, αλλά αυτή η τιμή μπορεί να αγνοηθεί, καθώς συνεισφέρει πολυωνυμική στο συνολική διάρκεια του προβλήματος. Εφόσον τα r και v έχουν καθοριστεί εκ των προτέρων, μπορούν να αυξήσουν το |U| και |C| σταθερό αριθμό φορών, άρα έχουμε |U| = O(p(n) 2) και |C| = O(p(n)) 2 . Επομένως, Μήκος = |U|| Γ| = O(p(n) 4) και, επομένως, οριοθετείται από ένα πολυώνυμο στο n, όπως απαιτείται. Έτσι, ο μετασχηματισμός f l μπορεί να υπολογιστεί από έναν αλγόριθμο που έχει πολυωνυμική χρονική πολυπλοκότητα (ωστόσο, το συγκεκριμένο πολυώνυμο που δεσμεύεται στην πολυπλοκότητα θα εξαρτηθεί από το L, καθώς και από την επιλογή των M και p), από τον οποίο μπορεί να εξαχθεί το συμπέρασμα ότι για όλα τα L ε NP η συνάρτηση f L είναι υπολογίσιμη σε πολυωνυμικό χρόνο και αντιστοιχίζει το L σε Lout (ακριβέστερα, αντιστοιχίζει το L σε Lout). Αυτό συνεπάγεται τον ισχυρισμό του θεωρήματος ότι το EP είναι ένα NP-πλήρες πρόβλημα.▀ Απόδειξη αποτελεσμάτων γιαNP-πληρότητα 3-ΦΥΣΙΜΟΤΗΤΑ (3-EX) ΚΑΤΑΣΤΑΣΗ. Δίνεται ένα σύνολο С= (с 1 , с 2 , ..., с m ) διαχωρισμών σε ένα πεπερασμένο σύνολο μεταβλητών U, έτσι ώστε |с i | = 3, 1 ≤ i ≤ m. ΕΡΩΤΗΣΗ. Υπάρχει ένα σύνολο τιμών αλήθειας στο U έτσι ώστε να ισχύουν όλοι οι διαχωρισμοί από το C; ΤΡΙΔΙΑΣΤΑΤΟΣ ΣΥΝΔΥΑΣΜΟΣ (3-C) ΚΑΤΑΣΤΑΣΗ. Δίνεται ένα σύνολο M ε W x X x Y, όπου τα W, X και Y είναι ασύνδετα σύνολα που περιέχουν τον ίδιο αριθμό στοιχείων q. ΕΡΩΤΗΣΗ. Είναι αλήθεια ότι το M περιέχει έναν τρισδιάστατο συνδυασμό, δηλ. ένα υποσύνολο M" ε M, έτσι ώστε |M`|=q και κανένα διαφορετικό στοιχείο του M" να έχει ίσες συντεταγμένες; ΚΟΡΥΦΟ ΕΞΩΦΥΛΛΟ (VP) ΚΑΤΑΣΤΑΣΗ. Δίνεται ένα γράφημα G =(V, E) και ένας θετικός ακέραιος αριθμός K, K ≤ |V|. ΕΡΩΤΗΣΗ. Έχει το γράφημα G κάλυψη κορυφής το πολύ K στοιχείων, δηλ. ένα υποσύνολο V" ε V έτσι ώστε |V`| ≤ K και για κάθε ακμή (u, v) ε E τουλάχιστον μία από τις κορυφές u ή v ανήκει στο v`; ΚΛΙΚΑ ΚΑΤΑΣΤΑΣΗ. Δίνεται γράφημα G=(V, E) και θετικός ακέραιος J ≤ |V|. ΕΡΩΤΗΣΗ. Είναι αλήθεια ότι το G περιέχει κάποια κλίκα καρδιαλικότητας τουλάχιστον J, δηλαδή, ένα υποσύνολο V` ε V έτσι ώστε |V`| ≥ Το J και οποιεσδήποτε δύο κορυφές στο V συνδέονται με μια ακμή στο E; ΧΑΜΙΛΤΟΝΙΚΟΣ ΚΥΚΛΟΣ (Hz) ΚΑΤΑΣΤΑΣΗ. Δίνεται γράφημα G=(V, E). ΕΡΩΤΗΣΗ. Είναι αλήθεια ότι το G περιέχει έναν κύκλο Χαμιλτονίου, δηλαδή μια τέτοια ακολουθία ΧΩΡΙΣΜΑ ΚΑΤΑΣΤΑΣΗ. Ένα πεπερασμένο σύνολο A και ένα «βάρος» s(a) ε Z+ δίνονται για κάθε a ε A. ΕΡΩΤΗΣΗ. Υπάρχει υποσύνολο Α" ε Α τέτοιο ώστε 3-σκοπιμότητα Το πρόβλημα 3-SATIBILITY είναι απλώς μια περιορισμένη έκδοση του προβλήματος SATIBILITY, στο οποίο κάθε μεμονωμένο πρόβλημα έχει ακριβώς τρία γράμματα σε κάθε διαχωρισμό.) Λόγω της απλής δομής του, αυτό το πρόβλημα χρησιμοποιείται συχνότερα για την απόδειξη NP-πλήρης αποτελεσμάτων. Θεώρημα 3.1.
Εργασία 3-ΕΦΙΣΙΜΟΤΗΤΑ είναιNP- πλήρης. Απόδειξη.Είναι εύκολο να δούμε ότι το 3-vyp ε NP. Αυτό προκύπτει από το γεγονός ότι ένας μη ντετερμινιστικός αλγόριθμος χρειάζεται μόνο να μαντέψει το σύνολο των τιμών αλήθειας των μεταβλητών του προβλήματος και να ελέγξει σε πολυωνυμικό χρόνο εάν θα ικανοποιηθούν όλες οι δοθέντες τριλίριοι διαχωρισμοί για αυτό το σύνολο τιμών αλήθειας. Ας μειώσουμε το πρόβλημα των δημοσίων σχέσεων στο πρόβλημα των 3-PR. Έστω U = (u 1 , u 2 , …, u n ) ένα σύνολο μεταβλητών και С= (с 1 , σ 2 , ..., σ m ) είναι ένα αυθαίρετο σύνολο διαχωρισμών που ορίζει ένα αυθαίρετο μεμονωμένο πρόβλημα από το PR. Ας κατασκευάσουμε ένα σύνολο C" τριλίτρων διαχωρισμών σε κάποιο σύνολο μεταβλητών U", έτσι ώστε το C" να ικανοποιείται εάν και μόνο εάν το C ικανοποιείται. Το σύνολο C" θα κατασκευαστεί αντικαθιστώντας κάθε επιμέρους διάζευξη c j ε C με ένα "ισοδύναμο" σύνολο C` j τριών κυριολεκτικών διαχωρισμών στο σύνολο U των αρχικών μεταβλητών και το σύνολο U" j ορισμένων πρόσθετων μεταβλητών και των μεταβλητών από το U" το j θα χρησιμοποιείται μόνο σε διαχωρισμούς από το C` j Με άλλα λόγια, Επομένως, είναι απαραίτητο μόνο να δείξουμε πώς, ξεκινώντας από το cj, μπορεί κανείς να κατασκευάσει τα C` j και U` j . Έστω c j από το σύνολο (z 1 , z 2 , ..., z k ), όπου z i , είναι κυριολεκτικά στο σύνολο U. Ο τρόπος που σχηματίζονται τα C` j και U" j εξαρτάται από την τιμή του k. Για να αποδείξουμε ότι η αναγωγιμότητα όντως λαμβάνει χώρα εδώ, είναι απαραίτητο να δείξουμε ότι το σύνολο των προτάσεων C" είναι ικανοποιητικό εάν και μόνο εάν ικανοποιούμε το σύνολο των προτάσεων C. Ας υποθέσουμε πρώτα ότι το t: → (T, F) είναι ένα σύνολο των τιμών αλήθειας, που ικανοποιούν το C. Ας δείξουμε ότι το t μπορεί να επεκταθεί σε ένα σύνολο τιμών αλήθειας t": U" → (T, P) που ικανοποιεί το C". Δεδομένου ότι οι μεταβλητές στο σύνολο U" \ U χωρίζονται σε ομάδες U` j και δεδομένου ότι οι μεταβλητές σε κάθε ομάδα U` j εμφανίζονται μόνο σε διαχωρισμούς που ανήκουν στο C` j , αρκεί να δείξουμε πώς το t μπορεί να επεκταθεί σε κάθε σύνολο U ` j χωριστά , και σε κάθε περίπτωση είναι απαραίτητο να ελέγχεται ότι πληρούνται όλες οι αποσυνδέσεις στο αντίστοιχο σύνολο C` j . Αυτό μπορεί να γίνει με τον ακόλουθο τρόπο. Εάν το U` j κατασκευάζεται όπως στην περίπτωση 1 ή 2, τότε οι διαχωρισμοί από το C` j έχουν ήδη γίνει κατά t, οπότε το t μπορεί να επεκταθεί στο U` j αυθαίρετα, για παράδειγμα, βάζοντας t "(y) = T για όλα y ε U" j . Αν το U" j έχει κατασκευαστεί όπως στην περίπτωση 3, τότε το U` j είναι κενό και ο μόνος διαχωρισμός στο C` j έχει ήδη γίνει με το t. Απομένει μόνο η περίπτωση 4, που αντιστοιχεί στον διαχωρισμό (z 1 , z 2 , . .. .. ., z k ) από το C και k > 3. Εφόσον το t είναι ένα ικανοποιητικό σύνολο τιμών αλήθειας για το C, τότε υπάρχει ένας ακέραιος αριθμός l τέτοιος ώστε το z l να γίνεται αληθές στο t. Αν l = 1 ή 2 , τότε θέτουμε t "(y i j) =F, 1 ≤ i ≤ k - 3. Αν l = k - 1 ή k, τότε θέτουμε t"(y i j) = F, 1 ≤ .i ≤ k - 3. Διαφορετικά , θέσαμε t"(y ij) = T για 1 ≤ i ≤ l -2 και t" (yij) = F για l-1 ≤ i ≤ k -3. Είναι εύκολο να ελέγξουμε ότι ένα τέτοιο σύνολο τιμών αλήθειας θα ικανοποιήσει όλους τους διαχωρισμούς στο C`j, οπότε το t` κάνει τα πάντα διαχωρισμούς από το C". Αντίθετα, εάν το t" είναι κάποιο ικανοποιητικό σύνολο τιμών αλήθειας για το C, τότε είναι εύκολο να ελεγχθεί ότι ο περιορισμός t" στις μεταβλητές από το U πρέπει να είναι ένα ικανοποιητικό σύνολο τιμών αλήθειας για το C. Έτσι, το C" ικανοποιείται αν και μόνο αν ικανοποιήσουμε το C . Προκειμένου να επαληθευτεί ότι αυτή η αναγωγιμότητα είναι πολυωνυμική, αρκεί να σημειωθεί ότι ο αριθμός των τριών γραμμάτων διαχωρισμού στο C" περιορίζεται από ένα πολυώνυμο σε κ.λπ. Επομένως, το μέγεθος ενός μεμονωμένου προβλήματος 3-RW οριοθετείται από πάνω από μερικά πολυωνυμικό στο μέγεθος του αντίστοιχου προβλήματος RW, και αφού όλες οι λεπτομέρειες Δεδομένου ότι οι κατασκευές της αναγωγιμότητας είναι προφανείς, δεν θα είναι δύσκολο για τον αναγνώστη να επαληθεύσει ότι αυτή η αναγωγιμότητα είναι πολυωνυμική.▀ Η περιορισμένη δομή του προβλήματος 3-RP το καθιστά πολύ πιο χρήσιμο στην απόδειξη NP-πλήρης αποτελεσμάτων από το πρόβλημα RP. Οποιαδήποτε απόδειξη που βασίζεται στο πρόβλημα RED (εκτός από αυτό που μόλις δόθηκε) μπορεί εύκολα να μετατραπεί σε απόδειξη που βασίζεται στο 3-RED, ακόμη και χωρίς αλλαγή της συνάρτησης που υλοποιεί τη μειωσιμότητα. Στην πραγματικότητα, η πρόσθετη προϋπόθεση ότι όλες οι διασταυρώσεις έχουν το ίδιο μήκος μπορεί συχνά να απλοποιήσει την αναγωγιμότητα που πρόκειται να κατασκευαστεί και έτσι να διευκολύνει την εύρεση. Επιπλέον, το πολύ μικρό μήκος των διαχωρισμών καθιστά δυνατή τη χρήση αναγωγιμότητας που δεν θα μπορούσε να κατασκευαστεί καθόλου για μεμονωμένα προβλήματα με διαχωρισμούς μεγαλύτερου μήκους. Αυτό υποδηλώνει ότι θα ήταν ακόμη καλύτερο εάν μπορούσαμε να δείξουμε ότι το ανάλογο πρόβλημα 2-SATIBILITY (κάθε διαχωρισμός περιέχει ακριβώς δύο κυριολεκτικά) είναι NP-complete. Ωστόσο, το 2-LEV μπορεί να λυθεί με τη μέθοδο "αναλύσεις" σε χρόνο που περιορίζεται από ένα πολυώνυμο στο γινόμενο του αριθμού των διαχωρισμών και του αριθμού των μεταβλητών ενός δεδομένου μεμονωμένου προβλήματος (βλ. επίσης), και, επομένως, ανήκει η τάξη Π. Υπάρχει ένα άλυτο πρόβλημα στα μαθηματικά. Το πρόβλημα του μάγειρα. Αν αντιμετωπίσουμε τη λύση του φιλοσοφικά, τότε λύθηκε εδώ και πολύ καιρό από πρόσωπα όπως ο Μέντελ. Το αποφάσιζε πιο γρήγορα από ό,τι έχει αποδειχθεί.... Αυτό είναι το πρόβλημα με τον Ταξιδιώτη. Και αυτό είναι ένα πρόβλημα... Σε πολλά μαθηματικά φόρουμ, δημοσίευσα ένα θέμα σχετικά με την εύρεση του ορίου μιας ακολουθίας. Όπου υπήρχαν κάποιες αυστηρά μαθηματικές προϋποθέσεις. Και παντού η απάντηση βρέθηκε εύκολα και ήταν η ίδια. Οριο Όταν όμως αποκαλύφθηκε το θέμα με τον Πούτνικ, από όπου, καταρχήν, ελήφθησαν οι υπολογισμοί με την ακολουθία των Χ και Υ, τότε ήταν ήδη δύσκολο να απαντηθεί. Και το ερώτημα δεν είναι, μου φαίνεται, δύσκολο. Ο ταξιδιώτης αποφάσισε να περπατήσει το μονοπάτι ενός άπειρου αριθμού τετραγώνων παρατεταγμένων σε μια σειρά, και ταυτόχρονα να πατήσει σε όλα τα τετράγωνα. Όμως, με κάθε νέα προσπάθεια, πρέπει να αυξάνει το μήκος του βήματος του. Έχει ο Ταξιδιώτης την ευκαιρία να πατήσει πάνω σε όλα ή σε έναν πεπερασμένο αριθμό τετραγώνων;! Λοιπόν...μήπως το πρόβλημα του Κουκ κρύβεται εδώ;! Μπορούμε εύκολα να προσδιορίσουμε το όριο της ακολουθίας Χ και η απάντηση με το σύνολο Χ (ο αριθμός των τετραγώνων που δεν θα πατήσει ο Ταξιδιώτης) δεν μπορεί πλέον να βρει την απάντηση. Κατ' αρχήν, η διαδικασία της διαδρομής του Ταξιδιώτη μπορεί να γραφτεί με άλλο τρόπο. Όχι μέσω της ποσότητας βηματοδότησης. 1 προσπάθεια. Αν ακολουθήσουμε το γεγονός ότι ο Ταξιδιώτης προχωρά σταδιακά τα πρώτα τετράγωνα από την αρχή, τότε το ίδιο το σύστημα των επιθέσεων δεν έχει σημασία και τελικά θα φτάσουμε σε 0 τετράγωνα που δεν πάτησε το πόδι του Ταξιδιώτη. Στη συνέχεια όμως θα δούμε: Εδώ για παράδειγμα από τα πρώτα 5 πατήσαμε το 2. Μένει 3. Μετά προσθέτουμε 4 και παίρνουμε 7. Γι' αυτό το ερώτημα των ερωτήσεων. Τελευταία επιστημονικά νέα
Βραβείο 1 εκατομμυρίου δολαρίων για την επίλυση καθενός από επτά μαθηματικά προβλήματα CMI - The Clay Mathematics Institute (Cambridge, Massachusetts) - ονόμασε επτά άλυτα μαθηματικά προβλήματα - "Millennium Prize Problems", για την επίλυση καθενός από τα οποία θα πληρωθεί 1 εκατομμύριο δολάρια. Λύσεις που δημοσιεύτηκαν σε γνωστό μαθηματικό περιοδικό είναι έγινε αποδεκτό για εξέταση και όχι νωρίτερα από 2 χρόνια μετά τη δημοσίευση (για ολοκληρωμένη εξέταση από τη μαθηματική κοινότητα). Ας απαριθμήσουμε αυτά τα προβλήματα: Το πρόβλημα του μάγειρα(διατυπώθηκε το 1971). Υπόθεση Riemann(διατυπώθηκε το 1859). Υπόθεση Birch και Swinnerton-Dyer. Υπόθεση Hodge. Εξισώσεις Navier-Stokes. Το πρόβλημα του Πουανκαρέ. Εξισώσεις Yang-Mills.
Ο Stephen Cook διατύπωσε το πρόβλημα ως εξής: μπορεί ο έλεγχος της ορθότητας μιας λύσης σε ένα πρόβλημα να είναι μεγαλύτερος από τη λήψη της ίδιας της λύσης, ανεξάρτητα από τον αλγόριθμο επαλήθευσης.
Το X είναι συν-άπειρο και το Y είναι 0.
Και αν στο πρώτο θέμα χρειαζόταν να βρεθεί το όριο της ακολουθίας Χ, τότε στην ερώτηση με το Wayfarer αυτό είναι το αποτέλεσμα του Χ. Δηλαδή πόσο δεν θα πατήσει ο Ταξιδιώτης.
Το όριο και το αποτέλεσμα είναι ένα και το αυτό. Αυτό για το οποίο επιδιώκει η δράση.
Μάλιστα, ο ταξιδιώτης περπάτησε Χ (1) τετράγωνα στην πρώτη προσπάθεια, Χ (2) στη δεύτερη ... κ.ο.κ.
Εν:
Δεν πρέπει το αποτέλεσμα να είναι 0 ή οποιοσδήποτε πεπερασμένος αριθμός, το αποτέλεσμα δεν θα πρέπει να είναι έτσι;:
X(1)>X(2)>X(3)>X(4)>...και ούτω καθεξής.
Αν τα τετράγωνα χωριστούν αριθμητικά σε ομάδες των 5 τετραγώνων, τότε παίρνουμε άπειρο αριθμό ομάδων των 5 τετραγώνων η καθεμία.
2 προσπάθεια.
Αν τα υπόλοιπα άθικτα τετράγωνα χωριστούν αριθμητικά σε ομάδες των 7 τετραγώνων, τότε θα πάρουμε άπειρο αριθμό ομάδων των 7 τετραγώνων η καθεμία.
Έτσι, έχοντας διανύσει το μονοπάτι, ο Ταξιδιώτης πάτησε 2 τετράγωνα σε κάθε ομάδα.
Τώρα από το 7 πατάμε στο 2 και παίρνουμε 5. Μετά προσθέτουμε το 6 στο 5, ώστε να είναι 11 στην ομάδα, και πατάμε στο 2. Μένουν 9.
Στη συνέχεια, προσθέστε 4 και λάβετε 13 στην ομάδα. Περάστε στο 2 και λάβετε 11.
Στη συνέχεια, προσθέστε 6 και λάβετε 17 στην ομάδα. Περάστε στο 2 και λάβετε 15.
Στη συνέχεια, προσθέστε 4 και λάβετε 19 στην ομάδα. Περάστε στο 2 και λάβετε 17.
Στη συνέχεια, προσθέστε 6 και λάβετε 23 στην ομάδα. Περάστε στο 2 και λάβετε 21.
Και ούτω καθεξής.
Τι βλέπουμε;
Δείτε πώς πήγε η αύξηση του ισοζυγίου μετά την έναρξη:
3..5..9..11...15...17...21..
Όπως μπορούμε να δούμε, το ποσό που δεν μπορούμε να πατήσουμε αυξάνεται ... και το σπρώχνουμε κάπως προς τα εμπρός ... Αν αφαιρέσουμε τα πρώτα. Όμως..τα τετράγωνά μας είναι «καρφωμένα» στο δρόμο και άρα αυτός ο αριθμός θα πρέπει να βρίσκεται στη θέση του.
Και αποδείχτηκε ΔΥΣΚΟΛΗ ερώτηση! Για να είμαι ειλικρινής, παλιά πίστευα διαφορετικά.
Και το ερώτημα είναι το ίδιο: «Πόσα τετράγωνα δεν πατάει ο Ταξιδιώτης; Δεν είναι άπειρο;!»
(βάσει υλικού από τον ιστότοπο http://www.claymath.org./prize_problems/index.htm)
Ας υποθέσουμε ότι, όντας σε μια μεγάλη εταιρεία, θέλετε να βεβαιωθείτε ότι ο φίλος σας είναι επίσης εκεί. Αν σας πουν ότι κάθεται στη γωνία, τότε αρκεί ένα κλάσμα του δευτερολέπτου για να βεβαιωθείτε με μια ματιά ότι οι πληροφορίες είναι αληθινές. Ελλείψει αυτών των πληροφοριών, θα αναγκαστείτε να περπατήσετε σε όλο το δωμάτιο, κοιτάζοντας τους καλεσμένους.
Με τον ίδιο τρόπο, εάν κάποιος σας πει ότι ο αριθμός 13717421 μπορεί να αναπαρασταθεί ως το γινόμενο δύο μικρότερων αριθμών, δεν είναι εύκολο να επαληθεύσετε γρήγορα την αλήθεια των πληροφοριών, αλλά αν σας πουν ότι ο αρχικός αριθμός μπορεί να παραγοντοποιηθεί με 3607 και 3803, τότε αυτή η δήλωση ελέγχεται εύκολα με μια αριθμομηχανή.
Αυτά τα παραδείγματα απεικονίζουν ένα κοινό φαινόμενο: η επίλυση ενός προβλήματος απαιτεί συχνά περισσότερο χρόνο από τον έλεγχο της ορθότητας της λύσης. Ο Stephen Cook διατύπωσε το πρόβλημα: μπορεί ο έλεγχος της ορθότητας μιας λύσης σε ένα πρόβλημα να είναι μεγαλύτερος από τη λήψη της ίδιας της λύσης, ανεξάρτητα από τον αλγόριθμο επαλήθευσης.
Αυτό το πρόβλημα είναι ένα από τα άλυτα προβλήματα της λογικής και της επιστήμης των υπολογιστών. Η λύση του θα μπορούσε να φέρει επανάσταση στις βασικές αρχές της κρυπτογραφίας που χρησιμοποιείται στη μετάδοση και αποθήκευση δεδομένων.
Ορισμένοι ακέραιοι αριθμοί δεν μπορούν να εκφραστούν ως το γινόμενο δύο μικρότερων ακεραίων, όπως 2, 3, 5, 7 κ.λπ. Αυτοί οι αριθμοί ονομάζονται πρώτοι αριθμοί και παίζουν σημαντικό ρόλο στα καθαρά μαθηματικά και τις εφαρμογές τους. Η κατανομή των πρώτων μεταξύ όλων των φυσικών αριθμών δεν ακολουθεί καμία κανονικότητα, ωστόσο, ο Γερμανός μαθηματικός Riemann (1826-1866) ανακάλυψε ότι ο αριθμός των πρώτων αριθμών που δεν υπερβαίνει το , εκφράζεται μέσω της κατανομής των μη τετριμμένων μηδενικών της συνάρτησης ζήτα Riemann. Ο Riemann εξέφρασε την εικασία, η οποία δεν έχει αποδειχθεί ή διαψευστεί μέχρι στιγμής, ότι όλα τα μη τετριμμένα μηδενικά της συνάρτησης ζήτα βρίσκονται σε μια ευθεία γραμμή. Μέχρι σήμερα, οι πρώτες 1500000000 λύσεις έχουν επαληθευτεί.
Οι μαθηματικοί έχουν από καιρό γοητευτεί από το πρόβλημα της περιγραφής όλων των λύσεων σε ακέραιους αριθμούς, , αλγεβρικές εξισώσεις, δηλαδή εξισώσεις σε πολλές μεταβλητές με ακέραιους συντελεστές. Ένα παράδειγμα αλγεβρικής εξίσωσης είναι η εξίσωση. Ο Ευκλείδης έδωσε μια πλήρη περιγραφή των λύσεων αυτής της εξίσωσης, αλλά για πιο σύνθετες εξισώσεις, η απόκτηση μιας λύσης γίνεται εξαιρετικά δύσκολη (για παράδειγμα, η απόδειξη ότι δεν υπάρχουν ακέραιες λύσεις σε μια εξίσωση).
Το 1970, ο Yuri Vladimirovich Matiyasevich έδωσε αρνητική λύση στο δέκατο πρόβλημα του Hilbert, δηλ. Δεν υπάρχει αλγόριθμος με τον οποίο θα μπορούσε κανείς να βρει εάν μια εξίσωση είναι επιλύσιμη σε ακέραιους αριθμούς ή όχι. Αλλά στη συγκεκριμένη περίπτωση όπου οι λύσεις σχηματίζουν μια ποικιλία Abelian, οι Birch και Swinnerton-Dyer πρότειναν ότι ο αριθμός των λύσεων καθορίζεται από την τιμή της συνάρτησης ζήτα που σχετίζεται με την εξίσωση στο σημείο 1: εάν η τιμή της συνάρτησης ζήτα στο σημείο Το 1 είναι 0, τότε υπάρχει άπειρος αριθμός λύσεων και αντίστροφα, αν όχι ίσο με 0, τότε υπάρχει μόνο ένας πεπερασμένος αριθμός τέτοιων λύσεων.
Τον εικοστό αιώνα, οι μαθηματικοί επινόησαν ισχυρές μεθόδους για τη μελέτη του σχήματος σύνθετων αντικειμένων. Η κύρια ιδέα είναι να μάθουμε σε ποιο βαθμό μπορούμε να προσεγγίσουμε το σχήμα ενός δεδομένου αντικειμένου κολλώντας μεταξύ τους απλά σώματα αυξανόμενης διάστασης. Αυτή η μέθοδος έχει αποδειχθεί αποτελεσματική στην περιγραφή μιας ποικιλίας αντικειμένων που συναντώνται στα μαθηματικά. Δυστυχώς, οι γεωμετρικές αιτιολογήσεις της μεθόδου δεν ήταν σαφείς: σε ορισμένες περιπτώσεις ήταν απαραίτητο να προστεθούν μέρη που δεν είχαν γεωμετρική ερμηνεία.
Η εικασία του Hodge είναι ότι για ιδιαίτερα καλούς τύπους χώρων, που ονομάζονται προβολικές αλγεβρικές ποικιλίες, τα λεγόμενα. Οι κύκλοι Hodge είναι συνδυασμοί αντικειμένων που έχουν γεωμετρική ερμηνεία - αλγεβρικοί κύκλοι.
Εάν πλεύσετε με μια βάρκα στη λίμνη, τότε θα προκύψουν κύματα, και εάν πετάξετε με αεροπλάνο, θα προκύψουν ταραχώδεις ροές στον αέρα. Υποτίθεται ότι αυτά και άλλα φαινόμενα περιγράφονται με εξισώσεις γνωστές ως εξισώσεις Navier-Stokes. Οι λύσεις αυτών των εξισώσεων δεν είναι γνωστές, ούτε καν είναι γνωστός ο τρόπος επίλυσής τους. Είναι απαραίτητο να δείξουμε ότι η λύση υπάρχει και είναι μια αρκετά ομαλή λειτουργία. Η λύση αυτού του προβλήματος θα καταστήσει δυνατή τη σημαντική αλλαγή των μεθόδων διεξαγωγής υδρο- και αεροδυναμικών υπολογισμών.
Εάν τεντώσετε ένα λάστιχο πάνω από ένα μήλο, τότε μπορείτε να μετακινήσετε αργά την ταινία χωρίς να αφήσετε την επιφάνεια, να τη συμπιέσετε σε ένα σημείο. Από την άλλη πλευρά, εάν το ίδιο λαστιχάκι τεντωθεί σωστά γύρω από το ντόνατ, δεν υπάρχει τρόπος να συμπιεστεί η ταινία σε ένα σημείο χωρίς να σκιστεί η ταινία ή να σπάσει το ντόνατ. Η επιφάνεια ενός μήλου λέγεται ότι είναι «απλά συνδεδεμένη» ενώ η επιφάνεια ενός ντόνατ όχι. Ο Πουανκαρέ ήξερε σχεδόν πριν από εκατό χρόνια ότι στη δισδιάστατη περίπτωση μόνο μια σφαίρα συνδέεται απλώς και έθεσε μια παρόμοια ερώτηση για μια τρισδιάστατη σφαίρα - ένα σύνολο σημείων σε τετραδιάστατο χώρο σε ίση απόσταση από κάποιο σημείο. Αποδείχθηκε ότι ήταν τόσο δύσκολο να αποδειχθεί ότι μόνο η σφαίρα είναι απλά συνδεδεμένη που οι μαθηματικοί εξακολουθούν να αναζητούν μια απάντηση.
Οι εξισώσεις της κβαντικής φυσικής περιγράφουν τον κόσμο των στοιχειωδών σωματιδίων. Πριν από σχεδόν πενήντα χρόνια, οι φυσικοί Yang και Mills, έχοντας ανακαλύψει τη σύνδεση μεταξύ γεωμετρίας και σωματιδιακής φυσικής, έγραψαν τις δικές τους εξισώσεις. Έτσι, βρήκαν έναν τρόπο να ενοποιήσουν τις θεωρίες ηλεκτρομαγνητικών, αδύναμων και ισχυρών αλληλεπιδράσεων. Οι εξισώσεις Yang-Mills υπονοούσαν την ύπαρξη σωματιδίων που έχουν πράγματι παρατηρηθεί σε εργαστήρια σε όλο τον κόσμο, συμπεριλαμβανομένων των Brookhaven, Stanford και CERN. Ως εκ τούτου, η θεωρία του μετρητή Yang-Mills είναι αποδεκτή από τους περισσότερους φυσικούς, παρά το γεγονός ότι στο πλαίσιο αυτής της θεωρίας δεν είναι ακόμα δυνατό να προβλεφθούν οι μάζες των στοιχειωδών σωματιδίων.
Φόρτωση...