Comment

Comment by calfuris

A problem in NP can have a (positive) solution verified in polynomial time. That's it. Requiring more than polynomial time to solve isn't part of the definition, and in fact it's an open question whether any problems in NP require more than polynomial time to solve.

Every single problem in P is in NP. What is believed but unproven is that some problems in NP are not in P.

parent calfuris 4 months ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton