2020-05-11

Final Exam Problem 8.

Sebrianne, Gurserrat, Michael
Define the following concepts and give an example: (a) universal Turing Machine, (b) co-r.e.-complete language, (c) co-NP complete language.
(a): U=" On input ⟨M,w⟩, where M is a TM and w is a string: Simulate M on input w. If M ever enters its accept state, accept; if M ever enters its reject or other halt state, reject."
(b): If L is in C and if for a class of Languages C, L' in C turing reduces. the complements of this are co-re complete
(c): a language that is the complement of an NP complete language
(Edited: 2020-05-11)
Sebrianne, Gurserrat, Michael Define the following concepts and give an example: (a) universal Turing Machine, (b) co-r.e.-complete language, (c) co-NP complete language. (a): U=" On input ⟨M,w⟩, where M is a TM and w is a string: Simulate M on input w. If M ever enters its accept state, accept; if M ever enters its reject or other halt state, reject." (b): If L is in C and if for a class of Languages C, L' in C turing reduces. the complements of this are co-re complete (c): a language that is the complement of an NP complete language
X