language

Question

Comments

i think it will be d .
It is still not know . so either it will be true or false. and definitely it is decidable it is NPc wich is a part of NP. which means it can be solved in polynomial time  .

---

I think same, in any case L is cfl

Answer 1

Integer factorization is in NP but not proved to be in NP-Hard or P. So, it can go either way in future. We have 3 choices for $L$ depending on this, but all the 3 choices are CFLs. So, we need not worry anything and just say $L$ is a CFL though we do not know exactly which CFL it is.

Answer 2

i think it will be d .
It is still not know . so either it will be true or false. and definitely it is decidable it is NPc wich is a part of NP. which means it can be solved in polynomial time  .

Comments

How i have to approach this kind of questions

---

this type of question actually require a knowledge about NPC and NP classes which were earlier in syllabus . now just remember some of the NPC's . like travelling salesman. 3cnf , 3sat . problems and i don't know actually a simple way , if u have to add something u need the operand s. likewise if u have to think u need that knowledge, no short trick . and don't be tensed. just see how this one is solved.

Answer 3

https://en.wikipedia.org/wiki/Integer_factorization
Prime Factorisation is One of the Undecidable problem..

So given Language is L = { w⊄w^r | w∊ (a+b)*}
Actually Given Problem is set of all Palindrome i.e. L = {WW^r | w∊ (a+b)*}


 

Comments

Since L={ w w^r | w is (a+b)⁺  } so L is always CFL right

---

it's integer factorization which i think is npc . https://www.quora.com/Is-the-prime-factorization-problem-in-NP-class-If-not-supposing-P-NP-would-RSA-encryption-and-other-such-algorithms-which-rely-on-prime-factorization-being-hard-be-rendered-ineffective

---

ShivanisrivarshiniYoooooo :D
Tendua : yess

Answer 4

may be cfl not confirm