P i kompleksitetsteori
(Omdirigert frå P (kompleksitet))
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
endreDø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
endre- 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