0
$\begingroup$

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?

$\endgroup$

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.