True or False. T = true, F = false, and O = open, meaning that the answer is not
ID: 3722555 • Letter: T
Question
True or False. T = true, F = false, and O = open, meaning that the answer is not known science at this time. In the questions below, P and NP denote P-time and NP-time, respectively. Turn this problems in on Monday March 5 True or False. T = true, F-false, and 0 : open, meaning that the answer is not known science at this time 2· (i)The set of strings that your high school algebra teacher would accept as legitimate expressions (ii)The language (e) consisting of just one string, the empty string, is NP-complete. Warning The empty language is N'P-complete. Warning. Think long and hard about this problem is a context-free language Think long and hard about this problem before you answer. It's not as easy as it seems before you answer. It's not as easy as it seems. (iv)There exists a polynomial time algorithm which finds the factors of any positive integer, where the input is given as a binary numeral (v)The language consisting of all strings over (a,b) which have more a's than b's is context-free (vi) 2.SAT is P.TIME. (vii) 3-SAT is P-TIME. (viii) Primality is p.TIME. (ix)--There is a P-TIME reduction of the halting problem to 3-SAT.Explanation / Answer
Answer)
1) True - The set of strings that your high school algebra teacher would accept as legitimate expressions is a context-free language. - The strings generated from the context free grammar as context free languages can be applied to algebra problems for syntactically correct algebra expressions and the algebra expressions would accept as legitimate expressions is a context-free language
2) True - The language consisting of just one string the empty string is NP-complete - Language consisting of just one string is NP-complete
3) False - The empty language is NP-complete - This is because the empty language and its compliment are never NP-complete
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.