Also known as computational complexity class
set of problems in computational complexity theory of related resource-based complexity
Komplexitetsklass är inom komplexitetsteori en mängd beräkningsproblem som har liknande resursbaserad komplexitet. En typisk komplexitetsklass har en definition likt: mängden av alla problem som kan lösas av en M med O(f(n)) mycket resurser R, där n är storleken på problemet. Till exempel är problem av komplexitetsklass NP de beslutsproblem som en icke-deterministisk turingmaskin kan lösa på polynomiell tid, medan klassen PSPACE är mängden av beslutsproblem som kan lösas av en deterministisk turingmaskin på polynomiellt utrymme. Enklare komplexitetsklasser definieras av tre faktorer: * Problemtypen. Den vanligaste typen är beslutsproblem, men komplexitetsklassen kan även definieras av funktionsproblem (till exempel optimeringsproblem). * Beräkningsmodell. Den vanligaste beräkningsmodellen är med en deterministisk turingmaskin, men de kan även definieras av icke-deterministiska turingmaskiner, booleska kretsar och kvantturingmaskiner. * Den begränsade resursen och begränsningarna. Exempel är "polynomiell tid" och "logaritmiskt utrymme". Många komplexitetsklasser kan karaktäriseras med den matematiska logik som krävs för att uttrycka dem.
Abstract from DBpedia / Wikipedia · CC BY-SA
via Wikidata sitelinks · CC0
Discovered by embedding cosine similarity (sentence-transformers MiniLM, 384-dim).