Τοπρόβλημα τηςΣυρακούσαςείναιπαραδειγματικόως δείγμα τηςπολυπλοκότηταςτης απλότητας.Είναι γνωστόκαι με άλλεςονομασίες όπωςτο πρόβλημα 3x+1, ηακολουθία του Collatz ήακόμα και ητσεχικήεικασία. Αυτότο φαινόμενοείναιενδεικτικό καιτης δυσκολίαςτου και τηςπαγκοσμιότητάςτου στον τομέατης θεωρίαςαριθμών καιτων διακριτώνμαθηματικών.Το παράδοξοτουπροβλήματοςπροέρχεται απότον φαινομενικάαπλό ορισμότου.

Έστω  n > 1    { εάν     n Є 2Ν      :  n → n/2
                         { εάν     n Є 2Ν+1  :  n → 3n +1 

Τότε ηεικασία είναιη εξής: ανχρησιμοποιήσουμεεπαγωγικάαυτόν τονορισμό,καταλήγουμε μεπεπερασμέναβήματα στον αριθμό1. Με άλλα λόγιααν ορίσουμε τηλέξη ύψοςως τον αριθμόβημάτων για νακαταλήξουμεστον αριθμό 1,τότε το ύψοςπρέπει ναείναι πεπερασμένο.

Ανπαραμείνουμεστο πλαίσιοτων φυσικώναριθμών με τησυμβατικήνοοτροπία, οίδιος ο Paul Erdφs θεωρούσεότι ταμαθηματικά πουγνωρίζουμε δενεπαρκούν γιανα λύσουν τοπρόβλημα τηςΣυρακούσας.Στηνπραγματικότητααυτό ισχύειακόμα και ανενσωματώσουμετο πρόβλημαστο μιγαδικόεπίπεδο καιχρησιμοποιήσουμεκαι τημιγαδική ανάλυση.Με άλλα λόγιααυτό τοπρόβλημα δενπροσφέρει μιαειδικήδυνατότηταόσον αφορά μιααποτελεσματικήεπίθεση. Καικάθευπολογισμόςπου έγινε πάνωσε αυτό το πρόβλημαενισχύει αυτήντην άποψη. Αυτόδεν σημαίνειβέβαια ότι τοπρόβλημα είναιάλυτο ακόμακαι αν θυμίζειαποτελέσματατης θεωρίαςκομψότητας.

Το άλλοπρόβλημαπροέρχεται απόμια καινοτόμαιδέα του John Conway, οοποίος απέδειξεότι ανμετατρέψουμετο πρόβλημα μετον εξής τρόπο:

Γενικεύουμετη διαίρεσηκαιχρησιμοποιούμεp τύπουςσε συνάρτησημε το υπόλοιποπου ανήκει στοσύνολο {0, 1, 2, …, p-1},τότε δενμπορούμε νααποφασίσουμεαν το πρόβλημαέχει λύση.

Αυτός οπροβληματισμόςδεν είναιασήμαντος καιθυμίζει τονανάλογο γιατην εικασίατου Riemann όπως τηδιευκρίνισε ο Gregory Chaitin.Βέβαια πρέπειναεπισημάνουμεότι το να μηνμπορούμε νααποδείξουμε τοθετικόαποτέλεσμαείναι μιαέμμεσηαπόδειξη ότι ηεικασίαισχύει. Διότιαν δεν ισχύεισημαίνει ότι υπάρχειαντιπαράδειγμακαι συνεπώςένας αλγόριθμοςμπορεί να τοβρει καιεπομένως νααποφασίσει.

Ταπρόσφατααποτελέσματατου Tomas Oliveira e Silva (Αύγουστος2005) δείχνουν ότιη εικασίαισχύει για n ≤ 6 . 2⁵⁸, πράγματο οποίοσημαίνει ότιδεν είμαστε σεμια εκφυλισμένηπερίπτωσηεικασίας ανκαι αυτό δεν αποτελείβέβαια μιααπόδειξη τουγενικούπλαισίου.

Υπάρχεικαι μια άλληαναλογικήεικασία όπως ηεικασία του Goldbach όμως η μεγάληδιαφορά είναιότι σε αυτήντην περίπτωσηγνωρίζουμε ένακάτω φράγμα μετάαπό το οποίο ηεικασίαισχύει. Για τοπρόβλημα τηςΣυρακούσας δενέχουμε ακόμαένα ανάλογοαποτέλεσμα.Συνεπώς ηαπλότητά τουπαραμένειπολύπλοκη.