What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?
2
$\begingroup$
$\endgroup$
7
$\begingroup$
$\endgroup$
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 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
