Easy and hard questions

Some questions about a system can be answered quickly, and some, as far as anyone knows, cannot. This lesson fixes the words that the rest of the guide uses for the difference.

• Time is counted against size. The size of a system is its number of variables and rules. A method runs in linear time when its work grows in proportion to the size, and in polynomial time when the work grows at most like a fixed power of the size, such as its square. Questions that polynomial time answers form the class P, and they count as easy.
• Deciding asks whether a system allows any state at all. For a 2-CNF it takes linear time (Aspvall, Plass and Tarjan 1979): each loop of implications forces its members to be equal, as in lesson 1.4, and the system allows nothing exactly when some loop forces a variable to equal its own negation. For a 3-CNF it is NP-complete (Cook 1971). An allowed state, once found, is easy to check, and every question whose answers are easy to check translates into this one, so a fast method for it would give fast methods for all of them. Such questions form the class NP, and a question into which all of NP translates is NP-hard. Whether P equals NP is open, and this guide does not address it.
• Expressing is not computing. Lesson 3.2 showed that three places are needed to express a knot, but expressing a relation and deciding a system of such relations are different questions. Lessons 4.2 and 4.3 show both an easy and a hard side.