This question is a bit vague. What are you trying to achieve? A lot of people use <ul> <li><a href="">Menu 1</a></li> <li><a href="">Menu 2</a></li> <li><a href="">Menu 3</a></li> </ul> HTML: .. for their navigation, in which case a <p> is not necessary, but its presence/absence makes no difference to seo.
I strongly suggest that also you add titles to your navigation links. These should be longer that the link text. For example, if you navigation link is "Shoes", the title could be "Shoes and Footwear". This title will appear to user as a tooltip when they hover over the link, and also is good for SEO. <ul> <li><a href="" title="">Menu 1</a></li> <li><a href="" title="">Menu 2</a></li> <li><a href="" title="">Menu 3</a></li> </ul> HTML: Cryo.
It's a good idea to use titles attributes on your links, but the big 3 search engines don't use them in their ranking algorithms.