According to this Wikipedia article on unary language every unary language has a binary variant. My question is that given a unary language is there an equivalent binary language in P that is P-Complete.

  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 2 '19 at 12:53

As said Yuval Filmus in the comment, some unary languages are undecidable, so they don't even have an equivalent binary language in P.

| cite | improve this answer | |
  • $\begingroup$ Thanks so much! $\endgroup$ – AKASH VETRIVEL Mar 28 '19 at 21:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.