From Wikipedia, the free encyclopedia
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 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.