What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
2
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.
answered Apr 15 '16 at 3:24
-
$\begingroup$ I am using it to show that Directed Hamilton Cycle ≤P Undirected Hamilton Cycle. $\endgroup$– El FufuApr 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$ Apr 15 '16 at 3:39