Το Tetris είναι NP-Complete!

Τελικά το να περιδιαβαίνεις τη wikipedia διαβάζοντας άσχετα άρθρα μπορεί να βγάλει λαβράκια! Διάβαζα λοιπόν που λέτε το άρθρο για το Tetris, και έμαθα ότι το Tetris είναι NP-Complete! Μου φαίνεται απίστευτο! Ακόμη και αν ξέρεις εκ των προτέρων ΟΛΑ τα κομμάτια που θα πέσουν, είναι αδύνατο να βρεις έναν αλγόριθμο που να μεγιστοποιεί το σκορ σου σε πολυωνυμικό χρόνο! Καταπληκτικό! Και για του λόγου το αληθές, ιδού το paper από το 2002.