Kompleksitet P
P er ei kompleksitetsklasse som beskriver alle beslutningsproblemer løsbare i polynomiell tid av ei deterministisk turingmaskin.
Det er ei av de mest fundamentale kompleksitetsklassene innenfor kompleksitetsteori. Cobhams avhandling sier at P er kompleksitetsklassa over alle problemer som er effektivt løsbare. Et stort spørsmål innen informatikken er om denne kompleksitetsklassa er lik NP. Dette er kjent som P=NP-problemet og det er det per dags dato intet bevis for. P er definert som ei delmengde av NP.
Eksempler
Eksempler på problemer som er løsbare i polynomiell tid og dermed i P er f.eks. å finne største fellesnevner. Flere problemer innenfor lineær programmering er kjent for å være 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
This article uses material from the Wikipedia Norsk (Bokmål) article P (kompleksitet), which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Innholdet er tilgjengelig under CC BY-SA 4.0 hvis ikke annet er angitt. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Norsk (Bokmål) (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.