2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am using it to show that Directed Hamilton Cycle ≤P Undirected Hamilton Cycle. $\endgroup$
    – El Fufu
    Apr 15, 2016 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, 2016 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.