ABSTRACT
P 1. See preposition, postposition. 2. The conventional abbreviation for phrase in such symbols as NP (= noun phrase), VP (= verb phrase), etc. 3. An abbreviation for patient in the SAP analysis of clause structure. 4. (italicized) In complexity theory, denoting the class of problems soluble in polynomial time on a deterministic Turing machine. Membership in P is widely taken as a hallmark of efficient computability: if a problem is not in P, it cannot be efficiently computed. This is so because all problems not in P have (so far as we know) only exponential time algorithms, and can only be solved by enumerating all possible solutions and testing them one by one. Cf. NP (sense 2).
