Polynomialzeitberechenbare Probleme

Attention

Klasse PTime, kurz P, der in Polynomialzeit (bzgl. Eingabegröße) berechenbaren Funktionen.

⇒ Für viele wichtige Probleme kennen wir keinen Polynomialzeitalgorithmus, können aber auch nicht beweisen, dass es keinen gibt.