True or False. T = true, F = false, and O = open, meaning that the answer is not

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. (i)The set of strings that your high school algebra teacher would accept as legitimate expressions is a context-free language (ii)The language (e consisting of just one string, the empty string, is N'P-complete. Warning Think long and hard about this problem before you answer. It's not as easy as it seems (ii)T The empty language is NP-complete. Warning. Think long and hard about this problem 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.TI ME. (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

1. True

2) false, we know that its deterministic and there is only one string no matter what so its not NP complete

3) True,we do not know the language and whatever we input we cant win that its NONdeterministic , hence its NP complete

4)False

5) True

6) True

7)FALSE

8) True

9)Open, we cant reduce halting to 3SAT

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.