P i kompleksitetsteori

P er ei kompleksitetsklasse som skildrar alle beslutningsproblem som kan løysast i polynomiell tid av ei deterministisk turingmaskin. Ho er ei av dei meste fundamentale kompleksitetsklassene innanfor kompleksitetsteori. Cobhams avhandling seier at P er kompleksitetsklassa over alle problem som er effektivt løysbare. Eit stort spørsmål innan informatikken er om denne kompleksitetsklassa er lik NP. Dette problemet er kjent som P=NP-problemet og det er det per dags dato inkje bevis for. P er definert som ei delmengde av NP.

Døme

Døme på problem som kan løysast i polynomiell tid og dermed i P er til dømes å finna største fellesnemnar. Fleire problem innanfor lineær programmering er òg kjende for å vera i P.

Litteratur

• Sipser, Michael (2006). Introduction to the Theory of Computation, 2nd Edition. Course Technology Inc. ISBN 0-534-95097-3.  Section 7.2: The Class P, side 256–263