P
Polynomial
Definition
In der theoretischen Informatik steht P (Polynomial) für die Komplexitätsklasse aller Entscheidungsprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können. Probleme in P gelten als effizient lösbar. Die Frage, ob P gleich NP ist, gehört zu den bedeutendsten ungelösten Problemen der Mathematik und Informatik.