DHAMPATH is the set of all the directed graphs which have a hamiltonian path. It's a well known NP-complete problem.

I know the proof of SAT's downward self-reducibility. Arora-Barak says Cook-Levin's proof shows that all NP-complete languages are downward self-reducible. How?

I feel DHAMPATH can directly be shown downward self-reducible without using Cook-Levin, but I am not able to. Can you give some hint?


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.