Open eClass - Univ. of the Aegean | Θεωρία Υπολογισμού [open] | Άσκηση αυτοαξιολόγησης - Ενότητα 7η (Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp)

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

321-6701 - Αλέξης Καπόρης

Άσκηση αυτοαξιολόγησης - Ενότητα 7η (Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp)

Ένα πρόβλημα είναι στο P αν:

a) μια μη ντετερμινιστική μηχανή Turing το επιλύει σε πολ/κο χρόνο

b) μια ντετερμινιστική μηχανή Turing το επιλύει σε πολ/κο χρόνο

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

Ένα πρόβλημα είναι στο ΝP αν:

a) μια μη ντετερμινιστική μηχανή Turing το επιλύει σε πολ/κο χρόνο

b) μια ντετερμινιστική μηχανή Turing το επιλύει σε πολ/κο χρόνο

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

Ένα μη επιλύσιμο πρόβλημα ανήκει:

a) στο P

b) στο NP

c) σε κανένα από τα άνω