(The statements verifiable in polynomial time by a deterministic Turing machine and solvable in polynomial time by a non-deterministic Turing machine are totally equivalent, and the proof can be found in many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7.3.).
(Οι βεβαιώσιμες δηλώσεις σε πολυωνιμικό χρόνο από μια ντετερμινιστική μηχανή Turing και λυμένες σε πολυωνιμικό χρόνο από μια μη ντετερμινιστική μηχανή Turing είναι εντελώς ισοδύναμες ,και η απόδειξη μπορεί να βρεθεί σε πολλά εγχειρίδια,για παράδειγμα εισαγωγή του Sipser στην υπολογιστική θεωρία,παράγραφος 7.3.).