Course : Θεωρία Υπολογισμού [open]

a)  να λύσουμε σε μη  ντετερμινιστικό πολ/κο χρόνο ένα πρόβλημα πλήρες στην NP

b) να λύσουμε σε   ντετερμινιστικό πολ/κο χρόνο ένα πρόβλημα  στην NP

c) να λύσουμε σε  ντετερμινιστικό πολ/κο χρόνο ένα πρόβλημα πλήρες στην NP

e) να λύσουμε σε  ντετερμινιστικό πολ/κο χρόνο κάθε πρόβλημα στην NP

a)  να αποδείξουμε ότι κάθε πρόβλημα στην NP απαιτεί τουλάχιστον εκθετικό  ντετερμινιστικό χρόνο

b) να αποδείξουμε ότι ένα πλήρες πρόβλημα στην NP απαιτεί τουλάχιστον εκθετικό  ντετερμινιστικό χρόνο

c) να αποδείξουμε ότι ένα πρόβλημα στην NP απαιτεί τουλάχιστον εκθετικό  ντετερμινιστικό χρόνο