What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?
1 Answer
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 FufuApr 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$ Apr 15, 2016 at 3:39