Polynomial-Time The class of decision problems solvable in polynomial time by a Turing machine. See the complexity zoo entry here. Known relationships Participates in Builds on Polynomial-Time P ⊆ BPP P ⊆ coNP P ⊆ NP poly P ⊆ RP P ⊆ ZPP