1
$\begingroup$

I know HAMPATH is NP complete problem. But is there a way to tell if it is either a NL or L problem? I tried searching a lot of places online but it feels like I am going nowhere. Thanks in advance for any leads

$\endgroup$

migrated from stackoverflow.com Nov 30 '15 at 4:35

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Hint: NL$\subseteq$P. $\endgroup$ – Yuval Filmus Nov 30 '15 at 6:05
1
$\begingroup$

We don't know whether HAMPATH belongs to L or to NL. However, since NL$\subseteq$P, if HAMPATH belonged to L or to NL then it would follow that P=NP, which is conjectured not to be the case. So probably HAMPATH doesn't belong to L or to NL.

$\endgroup$

Your Answer

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