# What does the $\leq_{\mathrm{P}}$ symbol mean?

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.

• I am using it to show that Directed Hamilton Cycle ≤P Undirected Hamilton Cycle. Apr 15 '16 at 3:28
• 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. Apr 15 '16 at 3:39