Class EXP

Hard definition

Set of all languages that can be decided using a Deterministic TM in exponential time

Set of all problems that can be solved using a deterministic algorithm with exponential time complexity (computed using Asymptotic Notation)

The same concept, for functions that can return anything (not just a single boolean)
All problems in EXP are obviously in FEXP
Problems in FEXP are NOT necessarily in EXP

$P \subset E X P$
Every problem in P is also in EXP:
- All problems that have a polynomial solution, also have an exponential solution
- All easy problems can be also solved very slowly! Just run an exponential useless loop at the end before returning the answer!
Problems in EXP are obviously not all in P

Either:

Create a TM that solves the problem in exponential number of steps in regard to length of input string
Write a pseudocode and express 4 things:
1. Input can be converted to binary using Binary encoding
2. Total number of executed instructions are AT MOST exponential
3. All intermediate results have AT MOST exponential size (VERY IMPORTANT)
4. All instructions take AT MOST exponential time to run
Reminder: P is in EXP! So if you have a solution in P, just write it!

You can't. (Maybe you can prove it's undecidable?)