Ένα από τα παλαιότερα ανοιχτά προβλήματα της θεωρίας γράφων φαίνεται πως βρήκε απάντηση χάρη στην τεχνητή νοημοσύνη. Η εικασία Dinitz-Garg-Goemans, που παρέμενε αναπάντητη για περίπου 30 χρόνια, αποδείχθηκε λανθασμένη, όταν το GPT-5.6 Pro εντόπισε ένα δομημένο αντιπαράδειγμα έπειτα από μόλις τέσσερις σύντομες προτροπές (prompts), συνολικής έκτασης μικρότερης των 60 λέξεων. Το μοντέλο εργάστηκε αυτόνομα για περίπου 5,5 ώρες μέχρι να καταλήξει στο αποτέλεσμα.
Το αντιπαράδειγμα δημοσιοποίησε στο X ο Ντμίτρι Ρίμπιν, συνιδρυτής της εταιρείας τεχνητής νοημοσύνης Autokernel. Η πρώτη προτροπή ζητούσε από το μοντέλο να «κάνει μια ανακάλυψη και να βρει ένα δομημένο αντιπαράδειγμα», ενώ οι τρεις επόμενες το παρότρυναν απλώς να συνεχίσει την αναζήτησή του. Σύμφωνα με τον ίδιο, είχε αφιερώσει πολλές εβδομάδες προσπαθώντας να λύσει το πρόβλημα, πριν αποφασίσει να αξιοποιήσει το ChatGPT.
Dinitz-Garg-Goemans conjecture is false. This graph theory problem was open for ~30 years.
— Dmitry Rybin (@DmitryRybin1) July 22, 2026
The graph below has fractional flow cost 58. Any unsplittable flow (with capacity violation <=15) has cost at least 60.
Chat with GPT 5.6 Pro where this was found: https://t.co/Oi2PQoab2h pic.twitter.com/3ihncPMpve
Η θεωρία γράφων αποτελεί έναν κλάδο των μαθηματικών που μελετά δίκτυα αποτελούμενα από κόμβους (ή κορυφές) και τις συνδέσεις μεταξύ τους. Η εικασία Dinitz-Garg-Goemans μπορεί να περιγραφεί ως ένα πρόβλημα βελτιστοποίησης στις μεταφορές: φανταστείτε ότι προϊόντα αποστέλλονται από μία αποθήκη σε πολλούς προορισμούς και μπορούν να διασπαστούν σε μικρότερες αποστολές, ακολουθώντας διαφορετικές διαδρομές. Η εικασία υποστήριζε ότι το ίδιο σύστημα θα μπορούσε πάντα να μετατραπεί σε ένα όπου κάθε αποστολή παραμένει ενιαία, χωρίς να αυξηθεί το συνολικό κόστος μεταφοράς. Το αντιπαράδειγμα του GPT-5.6 Pro δείχνει ότι αυτό δεν ισχύει σε όλες τις περιπτώσεις.
Ο Ρίμπιν δεν απάντησε σε αιτήματα δημοσιογράφων για σχόλιο, ωστόσο σε ανάρτησή του στο X έγραψε: «Ξέρω ότι τα αντιπαραδείγματα σε παλιές εικασίες έχουν γίνει πλέον σχεδόν… meme. Όμως πραγματικά νοιαζόμουν για αυτό το πρόβλημα και πέρασα πολλές εβδομάδες σκεπτόμενος πάνω σε αυτό».
Ο Κρις Μπόουμαν-Σκάργκιλ από το Πανεπιστήμιο του Γιορκ σημειώνει ότι στη μαθηματική κοινότητα υπάρχει ένα διαχρονικό αστείο σύμφωνα με το οποίο σχεδόν κάθε εικασία στη θεωρία γράφων αποδεικνύεται τελικά λανθασμένη.
«Σε πεδία όπως η θεωρία αριθμών ή η άλγεβρα, τα μοτίβα που ισχύουν σε απλές περιπτώσεις συχνά εξακολουθούν να ισχύουν και σε πιο σύνθετες. Αντίθετα, στη θεωρία γράφων η δομή μπορεί να αλλάξει δραματικά με την προσθήκη ακόμη και ενός ή δύο κόμβων. Έτσι εξηγείται γιατί τέτοιες εικασίες διατυπώνονται αλλά και γιατί είναι τόσο εύκολο να διαφύγουν εξαιρέσεις», αναφέρει.
Η συγκεκριμένη εξέλιξη έρχεται να προστεθεί σε μια σειρά πρόσφατων επιτυχιών της τεχνητής νοημοσύνης στον χώρο των μαθηματικών. Τον Μάιο, μοντέλο της OpenAI έλυσε μια εικασία δεκαετιών του Παλ Έρντος, ενώ νωρίτερα αυτή την εβδομάδα άλλο σύστημα τεχνητής νοημοσύνης παρουσίασε αντιπαράδειγμα για την Jacobian Conjecture, που παρέμενε ανοιχτή σχεδόν έναν αιώνα. Παράλληλα, χρήστες αναφέρουν ότι η AI έχει συμβάλει στην επίλυση μιας εικασίας Graffiti και ακόμη ενός προβλήματος θεωρίας γράφων. Οι εξελίξεις αυτές ήταν αρκετές ώστε να δημιουργηθεί ειδική ιστοσελίδα που καταγράφει τα μαθηματικά αποτελέσματα που επιτυγχάνονται με τη βοήθεια μοντέλων τεχνητής νοημοσύνης.
Ο Αμπισέκ Σάχα από το Queen Mary University of London εκτιμά ότι τα σημερινά μοντέλα AI είναι ήδη εξαιρετικά αποτελεσματικά σε συγκεκριμένες μαθηματικές εργασίες, αν και θεωρεί πως απέχουν ακόμη από το να αναπτύσσουν νέες θεωρίες για την επίλυση των πιο δύσκολων ανοιχτών προβλημάτων.
«Η τεχνητή νοημοσύνη είναι ήδη υπεράνθρωπη σε ορισμένα μαθηματικά καθήκοντα. Υπάρχουν ακόμη αρκετοί “χαμηλόκρεμαστοι καρποί”, προβλήματα δηλαδή που μπορούν να αποδειχθούν ή να διαψευστούν με ελάχιστη ανθρώπινη παρέμβαση. Η μεγαλύτερη πρόκληση είναι να κατευθύνει κανείς σωστά το σύστημα. Ωστόσο, δεν πιστεύω ότι έχει φτάσει ακόμη στο σημείο να δημιουργεί τη νέα θεωρία που απαιτείται για τις βαθύτερες ανοιχτές εικασίες», υπογραμμίζει.
Από την πλευρά του, ο Αλεξάντερ Γιονγκ από το Πανεπιστήμιο του Ιλινόις στο Urbana-Champaign θεωρεί ότι η τεχνητή νοημοσύνη θα εξελιχθεί σε αναπόσπαστο εργαλείο για τους μαθηματικούς, επιτρέποντάς τους να εγκαταλείπουν γρήγορα αδιέξοδες προσεγγίσεις και να επικεντρώνονται σε πιο υποσχόμενες κατευθύνσεις.
«Τα αντιπαραδείγματα δεν είναι τόσο εντυπωσιακά όσο μια πλήρης μαθηματική απόδειξη. Ωστόσο, πιστεύω ότι σύντομα η τεχνητή νοημοσύνη θα αποδείξει πολλές εικασίες, αξιοποιώντας την τεράστια γνώση της επιστημονικής βιβλιογραφίας και την ικανότητά της να δοκιμάζει αμέτρητες προσεγγίσεις. Οι εικασίες που θα αντέξουν στον έλεγχο της AI θα αποτελέσουν τις πραγματικά μεγάλες προκλήσεις για την ανθρώπινη καινοτομία», καταλήγει.
Με πληροφορίες από το Newscientist / Eu.36kr / Officechai
