Αρχικές Υποθέσεις, δυσκολία αναγνώρισης συμβολοσειράς από μη ντετερμινιστικό αυτόματο. Δυσκολία Κυρίαρχου Συνόλου μέσω Υπόθεσης Εκθετικού Χρόνου.