Χαρακτηρίζονται εκθετικοί ως προς input size αλλά πολυωνυμικοί ως προς την τιμή:
a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input
Και τα δύο είναι επιστημονικώς αποδεκτά, δεν είναι ντροπή ή λάθος να πεις ότι ένας ψευδοπολυωνυμικός είναι πολυωνυμικός ως προς την τιμή. Είναι δύο διαφορετικές μέθοδοι προσδιορισμού της πολυπλοκότητας, αυτή με βάση τα bits εισόδου την εκφράζει καλύτερα για μεγάλα ν, αλλά σίγουρα και ο χαρακτηρισμός ως προς την τιμή δεν είναι λάθος.
Να κι ένα ακόμα από τη wikipedia, ειδικά για το primality test που αναφέρεσαι:
For example, the complexity of primality tests and multiplication algorithms can be measured in two different ways: one in terms of the integers being tested or multiplied, and one in terms of the number of binary digits (bits) in those integers. For example, if n is the integer being tested for primality, trial division can test it in Θ(n1/2) arithmetic operations; but if n is the number of bits in the integer being tested for primality, it requires Θ(2n/2) time. In the fields of cryptography and computational number theory, it is more typical to define the variable as the number of bits in the input integers.
Εμείς τι επιλέγουμε να διδάξουμε στους μαθητές, ότι το ν είναι η τιμή του αριθμού που ελέγχουμε αν είναι πρώτος, ή ο αριθμός των bit του;
Φαντάσου το σαν τη Φυσική, όπου στο σχολείο τους διδάσκουν κλασσική μηχανική, και αργότερα στο πανεπιστήμιο μαθαίνουν ότι αυτά ίσχυαν μόνο για μικρές ταχύτητες και δεν ισχύουν όσο πλησιάζουμε την ταχύτητα του φωτός. Έτσι κι εδώ, όσο το ν αυξάνεται, το uniform μοντέλο δεν περιγράφει τόσο καλά τους αλγορίθμους που απειρίζουν τα bits του τύπου δεδομένων, αλλά δεν κάνουμε και επιστημονικό λάθος αν χρησιμοποιήσουμε το uniform μοντέλο στο Λύκειο για να μην κουράσουμε τους μαθητές.
Πάμε λίγο στο βιβλίο της ΑΕΠΠ. Αυτό σε πολλές περιπτώσεις λέει είτε πιο άμεσα είτε πιο έμμεσα ότι το μέγεθος του προβλήματος δεν ταυτίζεται με το μέγεθος της εισόδου, αλλά ένα παράδειγμα που μας ταιριάζει ιδιαίτερα εδώ είναι ο υπολογισμός fibonacci:
Η επαναληπτική διαδικασία, λοιπόν, βασίζεται σε ένα και μόνο βρόχο, άρα η πολυπλοκότητα της μεθόδου είναι τάξης O(n).
Είναι το ίδιο με το παράδειγμα "γράψε ν αριθμούς" του Γιώργου, με τον υπολογισμό της δύναμης, και με το trivial primarity test. Και το βιβλίο το λέει Ο(n), όχι εκθετικό.
Εν τέλει η ουσία νομίζω είναι ότι έχουμε δύο επιλογές:
είτε ακολουθούμε το πνεύμα του βιβλίου της ΑΕΠΠ και μετράμε την πολυπλοκότητα άλλοτε ως προς το μέγεθος της εισόδου, άλλοτε ως προς την τιμή κλπ, και τα ψευδοπολυωνυμικά προβλήματα τα αναφέρουμε είτε ως πολυωνυμικά (χωρίς επιστημονικό λάθος) είτε ως εκτός ύλης,
είτε μετράμε πάντα την πολυπλοκότητα σε σχέση με το μέγεθος της εισόδου σε bits, βγάζουμε λάθος κάμποσα παραδείγματα του βιβλίου, και βγάζουμε ένα σωρό απλούς αλγορίθμους (π.χ. γράψε ν αριθμούς) ως εκτός ύλης.
Ο λόγος που αναμείχθηκα στην παρούσα συζήτηση είναι επειδή η πρώτη επιλογή μου φαίνεται σοφότερη.
Καλό ΣΚ σε όλους!