(Proof idea:recursively use 3 to search the middle configuration and use V to verify both parts.) EXPSPACE=UczSPACE(2):Languages that can be decided in exponential space on a deterministic Turing machine. L=Uc=SPACE(O(log n)):Languages that can be decided in logarithmic space on a deterministic Turing machine. 2.Nondeterministic,Alternation,Advice and Randomness NTIME(t(n)):Languages that can be decided in time t(n)on a nondeterministic Turing machine. NP Uc=1 NTIME(n): Languages that can be decided in polynomial time on a nondeterministic Turing machine. ● Languages that can be verified in polynomial time on a deterministic Turing machine. NP-Complete:Problems in NP to which any other NP problem can be reduce. SAT,Clique,HamiltonianCycle,TSP,SubsetSum,IP,... While most problems in NP are either in P or NP-complete,there are also problems in between. Theorem (Ladner)If P#NP,then there are languages that are neither in P or NP-complete. There are some specific problems not known to be in P or NPC.Some examples:Polynomial Identity Testing,Graph Isomorphism,Factoring,DiscreteLog. One can also define NEXP,languages decidable in exponential time on a nondeterministic Turing machine.This class is of course very large.Inside the smaller class PSPACE,people defined more classes(Proof idea: recursively use ∃ to search the middle configuration and use ∀ to verify both parts.) 𝐄𝐗𝐏𝐒𝐏𝐀𝐂𝐄 = ⋃ 𝐒𝐏𝐀𝐂𝐄(2 𝑛 𝑐 ) 𝑐≥1 : Languages that can be decided in exponential space on a deterministic Turing machine. 𝐋 = ⋃ 𝐒𝐏𝐀𝐂𝐄(𝑂(log 𝑛)) 𝑐≥1 : Languages that can be decided in logarithmic space on a deterministic Turing machine. 2. Nondeterministic, Alternation, Advice and Randomness NTIME(𝑡(𝑛)): Languages that can be decided in time 𝑡(𝑛) on a nondeterministic Turing machine. 𝐍𝐏 = ⋃ 𝐍𝐓𝐈𝐌𝐄(𝑛 𝑐 ) 𝑐≥1 : ⚫ Languages that can be decided in polynomial time on a nondeterministic Turing machine. ⚫ Languages that can be verified in polynomial time on a deterministic Turing machine. NP-Complete: Problems in NP to which any other NP problem can be reduce. ⚫ SAT, Clique, HamiltonianCycle, TSP, SubsetSum, IP, … While most problems in NP are either in P or NP-complete, there are also problems in between. Theorem (Ladner) If 𝐏 ≠ 𝐍𝐏, then there are languages that are neither in P or NP-complete. There are some specific problems not known to be in P or NPC. Some examples: Polynomial Identity Testing, Graph Isomorphism, Factoring, DiscreteLog. One can also define NEXP, languages decidable in exponential time on a nondeterministic Turing machine. This class is of course very large. Inside the smaller class PSPACE, people defined more classes