Gibt es entscheidbare Sprachen, die garantiert nicht in P sind?
-
Hallo,
ob es Sprachen in NP gibt, die nicht in P sind, weiß ja niemand.
Aber wie sieht es z.B. mit EXPTIME aus? Gibt es da irgendein Entscheidungsproblem, von dem man zeigen kann, dass es in EXPTIME, aber nicht in P liegt?
-
Hab schon was gefunden:
http://www.inf.fu-berlin.de/lehre/SS04/19532-V/vorlesung14.pdf