Problems in P are about deciding whether an input passes or not, where there exists a 'turing machine/algorithm/black box' that will tell you if an input does,

Problems in P are about deciding whether an input passes or not, where there exists a 'turing machine/algorithm/black box' that will tell you if an input does, or does not pass in a 'fast way'. A simple example is graph coloring. The box contains a graph, you pass in a color for each node, and the box checks if there are no adjacent nodes with the same color. Note that this box has an input (the coloring) but also a sort of parameter (the graph) you can create many different instances of this box by just changing the graph. You could also add another parameter, call it K. This will be the maximum number of colors you can use. It is still easy for the box to check if a coloring fits this criteria. For problems in NP, there is an underlying set of boxes in P. The input to an NP problem is a set of parameters that describe a box in P. In other words, any input for an NP problem corresponds to a 'fast box'. The NP problem then asks, "is there any input this fast box will accept". Such an accepted input is called a witness, because it proves that the box created by the input to the NP problem is solvable. In the graph coloring example, instead of having a graph, a number of colors K, and a coloring to check, you now have: a graph and a number of colors, and the question 'can we find any coloring'. We transformed a 'check a solution' into a 'find if a solution exists'. A key element here is that someone attempting the NP problem gets to look inside the box, figure out how it works. In your example of 'you have to guess the number I thought of', you need to hand the guesser a box that will check that number. The guesser can then look inside the box to see how it works. So a simple comparison with a fixed value allows the guesser to 'read the hardcoded value from the source code'. Do note that the box in P has to be fully deterministic. In an NP problem, an input describes some parameters