It's a vast generalization of the cost to verify a problem/solution.

- P means polynomial - NP means nondeterministic polynomial

Roughly polynomial (P) represents the upper bound of the cost to verify, and the polynomial characterization says that given a problem with a certain input (e.g. the input can be the number of training examples in ML training set or the number of constraints/conditions in a general problem— e.g. all the places you want to visit on your next trip, given many "wants" in a group)

When the cost is polynomial relative to the input size it means it can only be finitely larger than the input - that's a characteristic of the polynomial which is just a finite sum of powers of x (the input).

When the cost is nondeterministic polynomial, one way to think about it in what is called a nondeterministic Turing machine. The nondeterministic part refers to the "states" that the machines can transition to from any current state. When the transition can happen to more than one state, we say it's non-deterministic— and can imagine it's determined by some probability.

The general assumption is that polynomial (P) is easier than nondeterministic polnomial (NP). This isn't necessarily the case as there can be arbitrarily large finite numbers (making P solutions intractible)

The P vs NP problem is one of the main open problems and generally considered a crank magnet and general confusion. For a good (likely the best) resource see https://scottaaronson.blog/