What does the notation P < NP exactly mean?

51 Views Asked by At

Over the last days I stepped two times over the notation P < NP, but I am not sure what it exactly means. I first saw it here:

P < NP In Our Stockings?
https://rjlipton.wordpress.com/2020/12/24/p-np-in-our-stockings/

And now here:

Toward Combinatorial Proof of P < NP Basic Approach (119-128)
https://www.cs.swansea.ac.uk/reports/yr2006/CSR7-2006.pdf

The abstract of the later paper says: "We present a plausibe “school-algebraic” condition C0 that infers, in Peano Arithmetic, the negative solution (abbr.: P < NP) to the familiar open problem P =? NP."

Is P < NP a stronger statement than P ≠ NP? And infering P < NP means here from PA+C0, and because C0 is doubtful, its not really a proof of P ≠ NP?

1

There are 1 best solutions below

0
On BEST ANSWER

The $<$ sign here means "strict containment"; since we know that $P$ is contained in $NP$ it's equivalent to saying that $P \neq NP$.

And infering P < NP means here from PA+C0, and because C0 is doubtful, its not really a proof of P ≠ NP?

Yes. It's not stated as clearly as it could be, but $C_0$ is an unproven conjecture.