What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?


It should have been defined wherever you've seen it used. It normally stands for polynomial-time reducibility of one kind or another; usually many-one reducibility.

  • $\begingroup$ I am using it to show that Directed Hamilton Cycle ≤P Undirected Hamilton Cycle. $\endgroup$ – El Fufu Apr 15 '16 at 3:28
  • 1
    $\begingroup$ Yep. So it's whatever version of polynomial-time reducibility you're using in your course. You need to check the definition given by your lecturer. $\endgroup$ – David Richerby Apr 15 '16 at 3:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.