a) λύνω το Α το πολύ σε πολ/κό χρόνο ως προς το χρόνο που λύνω το Β
b) λύνω το Α το πολύ σε πολ/κό χρόνο ως προς το χρόνο που λύνω το Β μόνο αν η αναγωγή είναι πολ/κου χρόνου
a) κάθε πρόβλημα της NP ανάγεται στο Α χωρίς να ξέρουμε το χρόνο της αναγωγής
b) κάθε πρόβλημα της NP σε πολ/κο χρόνο ανάγεται στο Α
c) το Α ανάγεται σε κάθε πρόβλημα της NP σε πολ/κο χρόνο
a) είναι υπερσύνολο της NP
b) χαρακτηρίζει την χρονική πολ/τητα της NP
c) έχει βρεθεί ότι έχει τομή με την P
a) ανάγω το Α στο Β
b) ανάγω το Β στο Α
c) ανάγω σε πολ/κο χρόνο το Α στο Β
d) ανάγω σε πολ/κο χρόνο το Β στο Α
