In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is considered. Consequently, hidden shift functions are injective. Although hardness for rigid structures also give hardness for class as a whole is there any other reason why this is done? Are hardness results like these also generalized for non-injective functions?


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.