How to prove that there is closure in NP for the reverse operation on strings?

108 Views Asked by At

I have a language A which is known to be in NP. I want to know that if I have the language $A^R$ which takes in $w^R$ which is a word of A but read in reverse will it still be in NP?

I tried to prove it by writing that: because A is in NP we have a certificat c and therefore a polynomial verificator. I therefore conclude that we can build another polynomial verificator V which will take in $w^R$ which is w read in reverse and $c^R$ which is the certificat of A but read in reverse. Because we can make V we conclude that $A^R$ is in NP.

Does my proof make sense or there is presence of circular reasoning? What should I do to have a correct proof or a more formal one?

1

There are 1 best solutions below

6
On BEST ANSWER

Hint: work directly with the definition of NP noting that you can reverse the contents of the input tape of a Turing machine in polynomial time.