Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise?

  • 1
    $\begingroup$ If it is in P, does it tell you anything about being NP? $\endgroup$ – Evil May 9 '18 at 3:43
  • $\begingroup$ @Evil Do you mean P=NP? $\endgroup$ – centrinok May 9 '18 at 3:56
  • $\begingroup$ I suggest reviewing the definitions of P and NP. You can consult our reference question. $\endgroup$ – Yuval Filmus May 9 '18 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.