[refulgentis]

If you're a fellow dropout like me, context:

"P" is the class of problems that can be solved by a deterministic Turing machine in polynomial time. "NP" stands for "nondeterministic polynomial time," and is the class of problems for which a solution can be _verified_ in polynomial time by a deterministic Turing machine, given the correct "hint" or "certificate." Every problem in P is also in NP, since if a problem can be solved in polynomial time, its solution can certainly be verified in polynomial time (just solve the problem again).

[crznp]

> (just solve the problem again).

Certainly P is a subset of NP, but is this statement always true?

Consider a Galton board where a marble is dropped into an array of pegs. At each peg, it can go left or right at random (assume it never bounces further). After some number of choices, it falls into a slot.

Finding a solution (a slot that a marble can fall into) is easy: drop one marble. But it could take many marbles to verify that a marble can fall into a given slot.

As described, that is easy: all left choices, all right choices, everything in between. But imagine that the choices aren't fair, directly observable, or linear (LR != RL). Then it gets tricky.

I've never thought about non-deterministic problems of that sort in the context of computational theory, but it isn't uncommon in nature.

[strangetortoise]

To make meaningful statements about P and NP problems, you probably need to be able to model your problem as a computational one.

If for example, you model it as a graph, with a peg represented by a node, and a bounce direction to another peg with a directed edge. Assign probabilities to all the edges. Then you cqn simply flood search outwards to the end of the graph, accumulating probabilities by multiplication. Any node on the boundary with probability higher than zero can be reached, given enough balls. This job is clearly in P.

I'm not sure it makes sense to talk about "P" for physical problems without a computational model, but I'm not a complexity theorist

[Alpha3031]

Strictly speaking, the fundamental complexity classes (in order: L, NL, P, NP, PSPACE, EXPTIME, NEXPTIME, EXPSPACE) apply only to decision problems, which pose yes/no questions. For example, it's commonly said that the Traveling Salesman Problem is NP-complete, but this only applies to the decision version of the problem: "Given graph G with edges weighted with positive integers and a maximum weight n, does there exist a Hamiltonian cycle through the vertices such that the sum of the weights of the edges used is at most n?" In addition, for a problem to be in NP, the polynomial-time-verifiable certificate only has to exist for yes instances, there is no need for it to also be verifiable that no such cycle exists (a problem verifiable in polynomial time for the no cases is in co-NP).

Decision problems are much easier to reason about, which is why they are used to construct and define the fundamental complexity classes, though it is certainly possible to define analogous classes for different types of problems. See for example, Krentel (1988) "The complexity of optimization problems", which considers TSP-OPT: https://doi.org/10.1016/0022-0000(88)90039-6