"Komplexitetsklass"@sv . . . . "Komplexitetsklass \u00E4r inom komplexitetsteori en m\u00E4ngd ber\u00E4kningsproblem som har liknande resursbaserad komplexitet. En typisk komplexitetsklass har en definition likt: m\u00E4ngden av alla problem som kan l\u00F6sas av en M med O(f(n)) mycket resurser R, d\u00E4r n \u00E4r storleken p\u00E5 problemet. Till exempel \u00E4r problem av komplexitetsklass NP de beslutsproblem som en icke-deterministisk turingmaskin kan l\u00F6sa p\u00E5 polynomiell tid, medan klassen PSPACE \u00E4r m\u00E4ngden av beslutsproblem som kan l\u00F6sas av en deterministisk turingmaskin p\u00E5 polynomiellt utrymme. Enklare komplexitetsklasser definieras av tre faktorer: \n* Problemtypen. Den vanligaste typen \u00E4r beslutsproblem, men komplexitetsklassen kan \u00E4ven definieras av funktionsproblem (till exempel optimeringsproblem). \n* Ber\u00E4kningsmodell. Den vanligaste ber\u00E4kningsmodellen \u00E4r med en deterministisk turingmaskin, men de kan \u00E4ven definieras av icke-deterministiska turingmaskiner, booleska kretsar och kvantturingmaskiner. \n* Den begr\u00E4nsade resursen och begr\u00E4nsningarna. Exempel \u00E4r \"polynomiell tid\" och \"logaritmiskt utrymme\". M\u00E5nga komplexitetsklasser kan karakt\u00E4riseras med den matematiska logik som kr\u00E4vs f\u00F6r att uttrycka dem."@sv . . . . . . . . . . . . . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u043A\u043B\u0430\u0441\u0441\u0430\u043C\u0438 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u043D\u0430\u0437\u044B\u0432\u0430\u044E\u0442\u0441\u044F \u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u044B\u0447\u0438\u0441\u043B\u0438\u0442\u0435\u043B\u044C\u043D\u044B\u0445 \u0437\u0430\u0434\u0430\u0447, \u043F\u0440\u0438\u043C\u0435\u0440\u043D\u043E \u043E\u0434\u0438\u043D\u0430\u043A\u043E\u0432\u044B\u0445 \u043F\u043E \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0432\u044B\u0447\u0438\u0441\u043B\u0435\u043D\u0438\u044F. \u0413\u043E\u0432\u043E\u0440\u044F \u0431\u043E\u043B\u0435\u0435 \u0443\u0437\u043A\u043E, \u043A\u043B\u0430\u0441\u0441\u044B \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u2014 \u044D\u0442\u043E \u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u0430 \u043F\u0440\u0435\u0434\u0438\u043A\u0430\u0442\u043E\u0432 (\u0444\u0443\u043D\u043A\u0446\u0438\u0439, \u043F\u043E\u043B\u0443\u0447\u0430\u044E\u0449\u0438\u0445 \u043D\u0430 \u0432\u0445\u043E\u0434 \u0441\u043B\u043E\u0432\u043E \u0438 \u0432\u043E\u0437\u0432\u0440\u0430\u0449\u0430\u044E\u0449\u0438\u0445 \u043E\u0442\u0432\u0435\u0442 0 \u0438\u043B\u0438 1), \u0438\u0441\u043F\u043E\u043B\u044C\u0437\u0443\u044E\u0449\u0438\u0445 \u0434\u043B\u044F \u0432\u044B\u0447\u0438\u0441\u043B\u0435\u043D\u0438\u044F \u043F\u0440\u0438\u043C\u0435\u0440\u043D\u043E \u043E\u0434\u0438\u043D\u0430\u043A\u043E\u0432\u044B\u0435 \u043A\u043E\u043B\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0440\u0435\u0441\u0443\u0440\u0441\u043E\u0432. \u0414\u043B\u044F \u043A\u0430\u0436\u0434\u043E\u0433\u043E \u043A\u043B\u0430\u0441\u0441\u0430 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043A\u0430\u0442\u0435\u0433\u043E\u0440\u0438\u044F \u0437\u0430\u0434\u0430\u0447, \u043A\u043E\u0442\u043E\u0440\u044B\u0435 \u044F\u0432\u043B\u044F\u044E\u0442\u0441\u044F \u00AB\u0441\u0430\u043C\u044B\u043C\u0438 \u0441\u043B\u043E\u0436\u043D\u044B\u043C\u0438\u00BB \u0432 \u0434\u0430\u043D\u043D\u043E\u043C \u043A\u043B\u0430\u0441\u0441\u0435. \u042D\u0442\u043E \u043E\u0437\u043D\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043E \u043B\u044E\u0431\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430 \u0438\u0437 \u043A\u043B\u0430\u0441\u0441\u0430 \u0441\u0432\u043E\u0434\u0438\u0442\u0441\u044F \u043A \u0442\u0430\u043A\u043E\u0439 \u0437\u0430\u0434\u0430\u0447\u0435, \u0438 \u043F\u0440\u0438\u0442\u043E\u043C \u0441\u0430\u043C\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043B\u0435\u0436\u0438\u0442 \u0432 \u043A\u043B\u0430\u0441\u0441\u0435. \u0422\u0430\u043A\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043D\u0430\u0437\u044B\u0432\u0430\u044E\u0442 \u043F\u043E\u043B\u043D\u044B\u043C\u0438 \u0437\u0430\u0434\u0430\u0447\u0430\u043C\u0438 (\u0430\u043D\u0433\u043B. -complete) \u0434\u043B\u044F \u0434\u0430\u043D\u043D\u043E\u0433\u043E \u043A\u043B\u0430\u0441\u0441\u0430. \u041D\u0430\u0438\u0431\u043E\u043B\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043D\u043E\u0439 \u043F\u043E\u043B\u043D\u043E\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u044F\u0432\u043B\u044F\u044E\u0442\u0441\u044F NP-\u043F\u043E\u043B\u043D\u0430\u044F \u0437\u0430\u0434\u0430\u0447\u0430. \u041F\u043E\u043B\u043D\u044B\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u2014 \u0443\u0434\u043E\u0431\u043D\u044B\u0439 \u0438\u043D\u0441\u0442\u0440\u0443\u043C\u0435\u043D\u0442 \u0434\u043B\u044F \u0434\u043E\u043A\u0430\u0437\u0430\u0442\u0435\u043B\u044C\u0441\u0442\u0432\u0430 \u0440\u0430\u0432\u0435\u043D\u0441\u0442\u0432\u0430 \u043A\u043B\u0430\u0441\u0441\u043E\u0432. \u0414\u043E\u0441\u0442\u0430\u0442\u043E\u0447\u043D\u043E \u0434\u043B\u044F \u043E\u0434\u043D\u043E\u0439 \u0442\u0430\u043A\u043E\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043F\u0440\u0435\u0434\u043E\u0441\u0442\u0430\u0432\u0438\u0442\u044C \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C, \u0440\u0435\u0448\u0430\u044E\u0449\u0438\u0439 \u0435\u0451 \u0438 \u043F\u0440\u0438\u043D\u0430\u0434\u043B\u0435\u0436\u0430\u0449\u0438\u0439 \u0431\u043E\u043B\u0435\u0435 \u043C\u0430\u043B\u0435\u043D\u044C\u043A\u043E\u043C\u0443 \u043A\u043B\u0430\u0441\u0441\u0443, \u0438 \u0440\u0430\u0432\u0435\u043D\u0441\u0442\u0432\u043E \u0431\u0443\u0434\u0435\u0442 \u0434\u043E\u043A\u0430\u0437\u0430\u043D\u043E."@ru . . . . . . . . "Na Teoria da Complexidade Computacional, uma Classe de Complexidade \u00E9 um conjunto de problemas relacionados aos recursos computacionais baseados em complexidade. Uma t\u00EDpica classe de complexidade \u00E9 definida da seguinte forma: O conjunto de problemas que podem ser resolvidos por uma m\u00E1quina abstrata M usando O(f(n)) de recurso R, onde n \u00E9 o tamanho da entrada. As mais simples classes de complexidade s\u00E3o definidas pelos seguintes fatores: Muitas classes de complexidade podem ser caracterizadas em termos da matem\u00E1tica l\u00F3gica, necess\u00E1ria para express\u00E1-las."@pt . . . . . . . . . "Komplexitetsklass \u00E4r inom komplexitetsteori en m\u00E4ngd ber\u00E4kningsproblem som har liknande resursbaserad komplexitet. En typisk komplexitetsklass har en definition likt: m\u00E4ngden av alla problem som kan l\u00F6sas av en M med O(f(n)) mycket resurser R, d\u00E4r n \u00E4r storleken p\u00E5 problemet. Till exempel \u00E4r problem av komplexitetsklass NP de beslutsproblem som en icke-deterministisk turingmaskin kan l\u00F6sa p\u00E5 polynomiell tid, medan klassen PSPACE \u00E4r m\u00E4ngden av beslutsproblem som kan l\u00F6sas av en deterministisk turingmaskin p\u00E5 polynomiellt utrymme. Enklare komplexitetsklasser definieras av tre faktorer:"@sv . . . . . . "In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other models of computation (e.g. probabilistic Turing machines, interactive proof systems, Boolean circuits, and quantum computers). The study of the relationships between complexity classes is a major area of research in theoretical computer science. There are often general hierarchies of complexity classes; for example, it is known that a number of fundamental time and space complexity classes relate to each other in the following way: NL\u2286P\u2286NP\u2286PSPACE\u2286EXPTIME\u2286EXPSPACE (where \u2286 denotes the subset relation). However, many relationships are not yet known; for example, one of the most famous open problems in computer science concerns whether P equals NP. The relationships between classes often answer questions about the fundamental nature of computation. The P versus NP problem, for instance, is directly related to questions of whether nondeterminism adds any computational power to computers and whether problems having solutions that can be quickly checked for correctness can also be quickly solved."@en . . . "Complexity class"@en . . . . . . . . . . . "En teoria de complexitat, una classe de complexitat \u00E9s un conjunt de problemes de decisi\u00F3 de complexitat relacionada. Una classe de complexitat t\u00EDpica t\u00E9 una definici\u00F3 de la forma: El conjunt de problemes que se poden resoldre per una m\u00E0quina abstracta M usant O (f(n)) del recurs R on n \u00E9s la mida de l'entrada. Les classes de complexitat estan relacionades amb la taxa de creixement de la necessitat de recursos a mesura que augmenta l'entrada n. \u00C9s una mesura abstracta i no dona uns requeriments de temps o espai en termes de segons o bytes, ja que per obtenir-los caldria tenir informaci\u00F3 de la implementaci\u00F3 concreta. La funci\u00F3 dins de l'expressi\u00F3 O(...) pot ser una constant, per algorismes que no els afecta la mida n, o una expressi\u00F3 amb un logaritme, una pot\u00E8ncia d'n com una expressi\u00F3 polinomial o moltes d'altres. La O es llegeix com \"d'ordre \". Pel prop\u00F2sit de teoria de la complexitat, alguns detalls de la funci\u00F3 es poden ignorar, per exemple diferents expressions polinomials es poden ajuntar en una sola classe. El recurs en q\u00FCesti\u00F3 pot ser temps, essencialment el nombre d'operacions b\u00E0siques que ha de realitzar una m\u00E0quina abstracta o espai (emmagatzemament). Per exemple, la classe NP \u00E9s el conjunt de problemes de decisi\u00F3 les solucions dels quals es poden comprovar per una m\u00E0quina de Turing no determinista en un temps polinomial, mentre que la classe PSPACE \u00E9s el conjunt de problemes que es poden solucionar per una m\u00E0quina de Turing determinista en un espai polinomial."@ca . . . . . . . . . "\u0642\u0633\u0645 \u062A\u0639\u0642\u064A\u062F"@ar . . . . "\u041A\u043B\u0430\u0441\u0441 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438"@ru . . . . . . "In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other model"@en . "\u590D\u6742\u6027\u7C7B"@zh . . . "\u0641\u064A \u0639\u0644\u0645 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u064A\u060C \u0642\u0633\u0645 \u062A\u0639\u0642\u064A\u062F \u0647\u064A \u0645\u062C\u0645\u0648\u0639\u0629 \u0645\u0646 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u0645\u064F\u062A\u0639\u0644\u0642\u0629 \u0628\u0627\u0644\u0627\u0633\u0627\u0633 \u0641\u064A\u0645\u0627 \u0628\u064A\u0646\u0647\u0627 \u0628\u0645\u0648\u0631\u062F \u0645\u064F\u0639\u064A\u0646\u060C \u0627\u063A\u0644\u0628 \u0627\u0644\u0627\u0642\u0633\u0627\u0645 \u0644\u062F\u064A\u0647\u0627 \u0627\u0644\u062A\u0639\u0631\u064A\u0641 \u0627\u0644\u062A\u0627\u0644\u064A: \u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u064A \u064A\u0645\u0643\u0646 \u062D\u0644\u0647\u0627 \u0628\u0648\u0627\u0633\u0637\u0629 \u0645\u0648\u0627\u0631\u062F \u062D\u064A\u062B \u0623\u0646\u064E\u0651 n \u0647\u0648 \u0637\u0648\u0644 \u0627\u0644\u0645\u064F\u062F\u062E\u0644. \u0639\u0644\u0649 \u0633\u0628\u064A\u0644 \u0627\u0644\u0645\u062B\u0627\u0644: \u0627\u0644\u0642\u0633\u0645 NP \u0647\u0648 \u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u064A \u064A\u0645\u0643\u0646 \u062D\u0644\u0647\u0627 \u0628\u0648\u0642\u062A \u062D\u062F\u0648\u062F\u064A (\u0623\u064A ) \u0628\u0648\u0627\u0633\u0637\u0629 \u0622\u0644\u0629 \u062A\u064A\u0648\u0631\u0646\u062C \u063A\u064A\u0631 \u062D\u062A\u0645\u064A\u0629\u060C \u0645\u062B\u0627\u0644 \u0622\u062E\u0631 \u0647\u0648 \u0627\u0644\u0642\u0633\u0645 \u0628\u064A\u0633\u0628\u0627\u064A\u0633 \u0648\u0647\u0648 \u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u064A \u064A\u0645\u0643\u0646 \u062D\u0644\u0647\u0627 \u0628\u0648\u0627\u0633\u0637\u0629 \u0622\u0644\u0629 \u062A\u064A\u0648\u0631\u0646\u062C \u062D\u062A\u0645\u064A\u0629 \u0648\u062A\u0633\u062A\u062E\u062F\u0645 \u0645\u0643\u0627\u0646 \u0627\u0636\u0627\u0641\u064A \u0637\u0648\u0644\u0647 \u062D\u062F\u0648\u062F\u064A (\u0623\u064A \u0627\u0646\u0647\u0627 \u062A\u0633\u062E\u062F\u0645 \u0645\u0643\u0627\u0646 \u0627\u0636\u0627\u0641\u064A). \u0627\u0644\u0627\u0642\u0633\u0627\u0645 \u0627\u0644\u0623\u0633\u0627\u0633\u064A\u0629 \u0645\u064F\u0639\u0631\u0641\u0629 \u062D\u0633\u0628 \u0627\u0644\u0645\u062A\u063A\u064A\u0631\u0627\u062A \u0627\u0644\u062A\u0627\u0644\u064A\u0629: \u0628\u0639\u0636 \u0627\u0644\u0627\u0642\u0633\u0627\u0645 \u064A\u0645\u0643\u0646 \u062A\u0634\u062E\u064A\u0635\u0647\u0627 \u0628\u0648\u0627\u0633\u0637\u0629 \u0627\u0644\u0645\u0646\u0637\u0642 \u0627\u0644\u0631\u064A\u0627\u0636\u064A \u0627\u0644\u0644\u0627\u0632\u0645 \u0644\u062A\u0639\u0631\u064A\u0641\u0647\u0627."@ar . . . . "\u0641\u064A \u0639\u0644\u0645 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u064A\u060C \u0642\u0633\u0645 \u062A\u0639\u0642\u064A\u062F \u0647\u064A \u0645\u062C\u0645\u0648\u0639\u0629 \u0645\u0646 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u0645\u064F\u062A\u0639\u0644\u0642\u0629 \u0628\u0627\u0644\u0627\u0633\u0627\u0633 \u0641\u064A\u0645\u0627 \u0628\u064A\u0646\u0647\u0627 \u0628\u0645\u0648\u0631\u062F \u0645\u064F\u0639\u064A\u0646\u060C \u0627\u063A\u0644\u0628 \u0627\u0644\u0627\u0642\u0633\u0627\u0645 \u0644\u062F\u064A\u0647\u0627 \u0627\u0644\u062A\u0639\u0631\u064A\u0641 \u0627\u0644\u062A\u0627\u0644\u064A: \u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u064A \u064A\u0645\u0643\u0646 \u062D\u0644\u0647\u0627 \u0628\u0648\u0627\u0633\u0637\u0629 \u0645\u0648\u0627\u0631\u062F \u062D\u064A\u062B \u0623\u0646\u064E\u0651 n \u0647\u0648 \u0637\u0648\u0644 \u0627\u0644\u0645\u064F\u062F\u062E\u0644. \u0639\u0644\u0649 \u0633\u0628\u064A\u0644 \u0627\u0644\u0645\u062B\u0627\u0644: \u0627\u0644\u0642\u0633\u0645 NP \u0647\u0648 \u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u064A \u064A\u0645\u0643\u0646 \u062D\u0644\u0647\u0627 \u0628\u0648\u0642\u062A \u062D\u062F\u0648\u062F\u064A (\u0623\u064A ) \u0628\u0648\u0627\u0633\u0637\u0629 \u0622\u0644\u0629 \u062A\u064A\u0648\u0631\u0646\u062C \u063A\u064A\u0631 \u062D\u062A\u0645\u064A\u0629\u060C \u0645\u062B\u0627\u0644 \u0622\u062E\u0631 \u0647\u0648 \u0627\u0644\u0642\u0633\u0645 \u0628\u064A\u0633\u0628\u0627\u064A\u0633 \u0648\u0647\u0648 \u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0627\u0644\u062A\u064A \u064A\u0645\u0643\u0646 \u062D\u0644\u0647\u0627 \u0628\u0648\u0627\u0633\u0637\u0629 \u0622\u0644\u0629 \u062A\u064A\u0648\u0631\u0646\u062C \u062D\u062A\u0645\u064A\u0629 \u0648\u062A\u0633\u062A\u062E\u062F\u0645 \u0645\u0643\u0627\u0646 \u0627\u0636\u0627\u0641\u064A \u0637\u0648\u0644\u0647 \u062D\u062F\u0648\u062F\u064A (\u0623\u064A \u0627\u0646\u0647\u0627 \u062A\u0633\u062E\u062F\u0645 \u0645\u0643\u0627\u0646 \u0627\u0636\u0627\u0641\u064A). \u0627\u0644\u0627\u0642\u0633\u0627\u0645 \u0627\u0644\u0623\u0633\u0627\u0633\u064A\u0629 \u0645\u064F\u0639\u0631\u0641\u0629 \u062D\u0633\u0628 \u0627\u0644\u0645\u062A\u063A\u064A\u0631\u0627\u062A \u0627\u0644\u062A\u0627\u0644\u064A\u0629: 1. \n* \u0646\u0648\u0639 \u0627\u0644\u0645\u0633\u0623\u0644\u0629 \u0627\u0644\u062D\u0633\u0627\u0628\u064A\u0629: \u0639\u0644\u0649 \u0627\u0644\u0627\u063A\u0644\u0628 \u0627\u0644\u0645\u0633\u0627\u0626\u0644 \u0647\u064A \u0645\u0633\u0627\u0626\u0644 \u062A\u0642\u0631\u064A\u0631 (decision problem), \u0648\u0644\u0643\u0646 \u0627\u0642\u0633\u0627\u0645 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u064A\u0645\u0643\u0646 \u062A\u0639\u0631\u064A\u0641\u0647\u0627 \u0623\u064A\u0636\u0627 \u0628\u0648\u0627\u0633\u0637\u0629 \u0645\u0633\u0627\u0626\u0644 \u062F\u0648\u0627\u0644 (function problem) \u0645\u062B\u0644 \u0627\u0644\u0642\u0633\u0645 FP \u0623\u0648 \u0645\u0633\u0627\u0626\u0644 \u0639\u062F (counting problem) \u0645\u062B\u0644 P# \u0623\u0648 \u0645\u0633\u0627\u0626\u0644 \u0627\u0633\u062A\u0645\u062B\u0627\u0644... 2. \n* \u0646\u0648\u0639 \u0646\u0645\u0648\u0630\u062C \u0627\u0644\u062D\u0633\u0627\u0628: \u0639\u0644\u0649 \u0627\u0644\u0627\u063A\u0644\u0628 \u0646\u0645\u0648\u0630\u062C \u0627\u0644\u062D\u0633\u0627\u0628 \u0647\u0648 \u0622\u0644\u0629 \u062A\u064A\u0648\u0631\u0646\u062C \u0627\u0644\u062D\u062A\u0645\u064A\u0629 \u0648\u0644\u0643\u0646 \u0627\u0644\u0639\u062F\u064A\u062F \u0645\u0646 \u0627\u0644\u0627\u0642\u0633\u0627\u0645 \u062A\u064F\u0639\u0631\u0641 \u0628\u0627\u0644\u0629 \u062A\u064A\u0648\u0631\u0646\u062C \u063A\u064A\u0631 \u062D\u062A\u0645\u064A\u0629\u060C \u062F\u0648\u0627\u0626\u0631 \u0628\u0648\u0644\u064A\u0627\u0646\u064A\u0629\u060C \u0622\u0644\u0629 \u062A\u064A\u0648\u0631\u0646\u062C \u0643\u0645\u0648\u0645\u064A\u0629... 3. \n* \u0627\u0644\u0645\u0648\u0631\u062F \u0627\u0644\u0630\u064A \u064A\u062A\u0645 \u062A\u062D\u062F\u064A\u062F\u0647 \u0648\u0627\u0644\u062D\u062F\u0648\u062F: \u0645\u062B\u0644 \u00AB\u0648\u0642\u062A \u062D\u062F\u0648\u062F\u064A\u00BB, \u00AB\u0645\u0643\u0627\u0646 \u062D\u062F\u0648\u062F\u064A\u00BB, \u00AB\u0648\u0642\u062A \u0644\u0648\u062C\u0627\u0631\u062B\u0645\u064A\u00BB, ... \u0628\u0639\u0636 \u0627\u0644\u0627\u0642\u0633\u0627\u0645 \u064A\u0645\u0643\u0646 \u062A\u0634\u062E\u064A\u0635\u0647\u0627 \u0628\u0648\u0627\u0633\u0637\u0629 \u0627\u0644\u0645\u0646\u0637\u0642 \u0627\u0644\u0631\u064A\u0627\u0636\u064A \u0627\u0644\u0644\u0627\u0632\u0645 \u0644\u062A\u0639\u0631\u064A\u0641\u0647\u0627."@ar . . . . . . . . . "En informatique th\u00E9orique, et plus pr\u00E9cis\u00E9ment en th\u00E9orie de la complexit\u00E9, une classe de complexit\u00E9 est un ensemble de probl\u00E8mes algorithmiques dont la r\u00E9solution n\u00E9cessite la m\u00EAme quantit\u00E9 d'une certaine ressource. Une classe est souvent d\u00E9finie comme l'ensemble de tous les probl\u00E8mes qui peuvent \u00EAtre r\u00E9solus sur un mod\u00E8le de calcul M, utilisant une quantit\u00E9 de ressources du type R, o\u00F9 n, est la taille de l'entr\u00E9e. Les classes les plus usuelles sont celles d\u00E9finies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace. On peut par exemple citer les classes P et NP."@fr . . . "En teoria de complexitat, una classe de complexitat \u00E9s un conjunt de problemes de decisi\u00F3 de complexitat relacionada. Una classe de complexitat t\u00EDpica t\u00E9 una definici\u00F3 de la forma: El conjunt de problemes que se poden resoldre per una m\u00E0quina abstracta M usant O (f(n)) del recurs R on n \u00E9s la mida de l'entrada."@ca . . . . . . "Nella teoria della complessit\u00E0 computazionale, una classe di complessit\u00E0 \u00E8 un insieme di problemi di una certa complessit\u00E0. Un esempio tipico di definizione di classe di complessit\u00E0 ha la forma: l'insieme di problemi che, se esiste la soluzione, possono essere risolti da una macchina astratta M usando della risorsa R, con dimensione dell'input Molte classi di complessit\u00E0 possono essere caratterizzate in termini della logica matematica necessaria ad esprimerle; vedi . Gli possono essere usati per definire classi di complessit\u00E0 senza riferirsi ad un concreto."@it . "En teor\u00EDa de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisi\u00F3n de complejidad relacionada. Una clase de complejidad tiene una definici\u00F3n de la forma:"@es . . . . . . . . . . . . "76250"^^ . . . . "\u5728\u8A08\u7B97\u8907\u96DC\u5EA6\u7406\u8AD6\u4E2D\uFF0C\u4E00\u500B\u8907\u96DC\u5EA6\u985E\u6307\u7684\u662F\u4E00\u7FA4\u8907\u96DC\u5EA6\u985E\u4F3C\u7684\u554F\u984C\u7684\u96C6\u5408\u3002\u4E00\u500B\u5178\u578B\u7684\u8907\u96DC\u5EA6\u985E\u7684\u5B9A\u7FA9\u6709\u4EE5\u4E0B\u5F62\u5F0F\uFF1A \u53EF\u4EE5\u88AB\u540C\u4E00\u500B\u62BD\u8C61\u6A5F\u5668M\u4F7F\u7528O(f(n))\u7684\u8CC7\u6E90R\u6240\u89E3\u6C7A\u7684\u554F\u984C\u7684\u96C6\u5408\uFF08n\u662F\u8F38\u5165\u8CC7\u6599\u7684\u5927\u5C0F\uFF09\u3002 \u4F8B\u5982NP\u985E\u5225\u5C31\u662F\u4E00\u7FA4\u53EF\u4EE5\u88AB\u4E00\u975E\u78BA\u5B9A\u578B\u5716\u9748\u6A5F\u4EE5\u591A\u9805\u5F0F\u6642\u9593\u89E3\u6C7A\u7684\u6C7A\u5B9A\u578B\u554F\u984C\u3002\u800CP\u985E\u5225\u5247\u662F\u4E00\u7FA4\u53EF\u4EE5\u88AB\u78BA\u5B9A\u578B\u5716\u9748\u6A5F\u4EE5\u591A\u9805\u5F0F\u6642\u9593\u89E3\u6C7A\u7684\u6C7A\u5B9A\u578B\u554F\u984C\u3002\u67D0\u4E9B\u8907\u96DC\u5EA6\u985E\u662F\u4E00\u7FA4\u51FD\u5F0F\u554F\u984C\u7684\u96C6\u5408\uFF0C\u4F8B\u5982\u3002 \u8A31\u591A\u8907\u96DC\u5EA6\u985E\u53EF\u70BA\u6578\u5B78\u908F\u8F2F\u6240\u63CF\u8FF0\u523B\u5283\uFF0C\u8ACB\u898B\u3002 \u5E03\u76E7\u59C6\u8907\u96DC\u5EA6\u5247\u4E0D\u9700\u5BE6\u969B\u62BD\u8C61\u6A5F\u5668\u5C31\u53EF\u5B9A\u7FA9\u8907\u96DC\u5EA6\u985E\u3002"@zh . . . . . "In der Komplexit\u00E4tstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bez\u00FCglich einer bestimmten Ressource, meist bez\u00FCglich des Zeitaufwands oder des (Speicher-)Platzaufwands. Bei Problemen wird dabei stets das \u201Ekosteng\u00FCnstigste\u201C L\u00F6sungsverfahren angenommen. Der Aufwand ist im Allgemeinen abh\u00E4ngig von der \u201EGr\u00F6\u00DFe\u201C der Eingabe, wie viele Elemente sie umfasst. Abgesch\u00E4tzt wird der asymptotische Aufwand, also f\u00FCr sehr viele Eingabeelemente. Dabei zeigt sich, dass die Probleme bzgl. ihres Aufwands Gruppen bilden, deren Aufwand f\u00FCr gro\u00DFe Eingabemengen auf \u00E4hnliche Weise anw\u00E4chst; diese Gruppen werden Komplexit\u00E4tsklassen genannt. Eine Komplexit\u00E4tsklasse ist eine Menge von Problemen, welche sich in einem bestimmten ressourcenbeschr\u00E4nkten Berechnungsmode"@de . . . . . . . . . . . . "\uBCF5\uC7A1\uB3C4 \uC885\uB958"@ko . . . . . . . . . . . . . . . . . . "Classe di complessit\u00E0"@it . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u043A\u043B\u0430\u0441\u0441\u0430\u043C\u0438 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u043D\u0430\u0437\u044B\u0432\u0430\u044E\u0442\u0441\u044F \u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u044B\u0447\u0438\u0441\u043B\u0438\u0442\u0435\u043B\u044C\u043D\u044B\u0445 \u0437\u0430\u0434\u0430\u0447, \u043F\u0440\u0438\u043C\u0435\u0440\u043D\u043E \u043E\u0434\u0438\u043D\u0430\u043A\u043E\u0432\u044B\u0445 \u043F\u043E \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0432\u044B\u0447\u0438\u0441\u043B\u0435\u043D\u0438\u044F. \u0413\u043E\u0432\u043E\u0440\u044F \u0431\u043E\u043B\u0435\u0435 \u0443\u0437\u043A\u043E, \u043A\u043B\u0430\u0441\u0441\u044B \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u2014 \u044D\u0442\u043E \u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u0430 \u043F\u0440\u0435\u0434\u0438\u043A\u0430\u0442\u043E\u0432 (\u0444\u0443\u043D\u043A\u0446\u0438\u0439, \u043F\u043E\u043B\u0443\u0447\u0430\u044E\u0449\u0438\u0445 \u043D\u0430 \u0432\u0445\u043E\u0434 \u0441\u043B\u043E\u0432\u043E \u0438 \u0432\u043E\u0437\u0432\u0440\u0430\u0449\u0430\u044E\u0449\u0438\u0445 \u043E\u0442\u0432\u0435\u0442 0 \u0438\u043B\u0438 1), \u0438\u0441\u043F\u043E\u043B\u044C\u0437\u0443\u044E\u0449\u0438\u0445 \u0434\u043B\u044F \u0432\u044B\u0447\u0438\u0441\u043B\u0435\u043D\u0438\u044F \u043F\u0440\u0438\u043C\u0435\u0440\u043D\u043E \u043E\u0434\u0438\u043D\u0430\u043A\u043E\u0432\u044B\u0435 \u043A\u043E\u043B\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0440\u0435\u0441\u0443\u0440\u0441\u043E\u0432. \u041F\u043E\u043B\u043D\u044B\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u2014 \u0443\u0434\u043E\u0431\u043D\u044B\u0439 \u0438\u043D\u0441\u0442\u0440\u0443\u043C\u0435\u043D\u0442 \u0434\u043B\u044F \u0434\u043E\u043A\u0430\u0437\u0430\u0442\u0435\u043B\u044C\u0441\u0442\u0432\u0430 \u0440\u0430\u0432\u0435\u043D\u0441\u0442\u0432\u0430 \u043A\u043B\u0430\u0441\u0441\u043E\u0432. \u0414\u043E\u0441\u0442\u0430\u0442\u043E\u0447\u043D\u043E \u0434\u043B\u044F \u043E\u0434\u043D\u043E\u0439 \u0442\u0430\u043A\u043E\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043F\u0440\u0435\u0434\u043E\u0441\u0442\u0430\u0432\u0438\u0442\u044C \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C, \u0440\u0435\u0448\u0430\u044E\u0449\u0438\u0439 \u0435\u0451 \u0438 \u043F\u0440\u0438\u043D\u0430\u0434\u043B\u0435\u0436\u0430\u0449\u0438\u0439 \u0431\u043E\u043B\u0435\u0435 \u043C\u0430\u043B\u0435\u043D\u044C\u043A\u043E\u043C\u0443 \u043A\u043B\u0430\u0441\u0441\u0443, \u0438 \u0440\u0430\u0432\u0435\u043D\u0441\u0442\u0432\u043E \u0431\u0443\u0434\u0435\u0442 \u0434\u043E\u043A\u0430\u0437\u0430\u043D\u043E."@ru . . . . . . . . "De complexiteitsgraad van een bepaald algoritme is de manier waarop dat algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt."@nl . . . . . . . . . . . "Klasa z\u0142o\u017Cono\u015Bci"@pl . . . . . . . . . . . . . . "Classe de complexitat"@ca . . . . . . . "Complexiteitsgraad"@nl . . . . . . . . . . . "Na Teoria da Complexidade Computacional, uma Classe de Complexidade \u00E9 um conjunto de problemas relacionados aos recursos computacionais baseados em complexidade. Uma t\u00EDpica classe de complexidade \u00E9 definida da seguinte forma: O conjunto de problemas que podem ser resolvidos por uma m\u00E1quina abstrata M usando O(f(n)) de recurso R, onde n \u00E9 o tamanho da entrada. Por exemplo, a classe NP \u00E9 o conjunto de problemas decid\u00EDveis que podem ser resolvidos por uma M\u00E1quina de Turing N\u00E3o-Determin\u00EDstica em tempo polinomial, onde a classe PSPACE \u00E9 o conjunto de problemas decid\u00EDveis que podem ser resolvidos por uma M\u00E1quina de Turing Determin\u00EDstica em espa\u00E7o polinomial. As mais simples classes de complexidade s\u00E3o definidas pelos seguintes fatores: \n* O tipo de problema computacional: os mais comumentes usados s\u00E3o o problemas de decis\u00E3o. Contudo, classes de complexidade podem ser definidas baseadas nos problemas funcionais (Um exemplo \u00E9 o conjunto FP), problemas de contagem (Ex. #P), problemas de otimiza\u00E7\u00E3o, problemas de promessa, etc. \n* O modelo de computa\u00E7\u00E3o: o modelo de computa\u00E7\u00E3o mais comum \u00E9 a M\u00E1quina de Turing Determin\u00EDstica, por\u00E9m, muitas classes de complexidade s\u00E3o baseadas em M\u00E1quinas de Turing N\u00E3o-Determin\u00EDticas, circuitos booleanos, M\u00E1quina de Turing Qu\u00E2ntica, circuitos mon\u00F3tonos, etc. \n* O(s) recurso(s) que est\u00E1(\u00E3o) sendo limitado(os) e os limites: Estas duas propriedades s\u00E3o usualmente declaradas juntas, assim como \"tempo polinomial\", \"espa\u00E7o logar\u00EDtmico\", \"constante de profundidade\", etc. Muitas classes de complexidade podem ser caracterizadas em termos da matem\u00E1tica l\u00F3gica, necess\u00E1ria para express\u00E1-las. Delimitar o tempo computacional por cima por alguma fun\u00E7\u00E3o concreta f(n) muitas vezes produz classes de complexidade que dependem da escolha do modelo da m\u00E1quina. Por exemplo, a linguagem {xx| x \u00E9 uma cadeia bin\u00E1ria} pode ser decidida em tempo linear numa M\u00E1quina de Turing Multi-Fita, mas necessariamente requer um tempo exponencial no modelo da M\u00E1quina de Turing de fita simples. Se n\u00F3s permitirmos um varia\u00E7\u00E3o polinomial em tempo de execu\u00E7\u00E3o, a tese de Cobham-Edmonds afirma que, \"as complexidades de tempo em dois modelos razo\u00E1veis e gerais s\u00E3o polinomialmente relacionados\" (Goldreich 2008, Cap\u00EDtulo 1.2). Esti forma a base da classe de complexidade P, a qual \u00E9 o conjunto de problemas resolvidos por uma M\u00E1quina de Turing Determin\u00EDstica dentro de um tempo polinomial. O conjunto correspondente de problemas funcionais para P \u00E9 FP. Os axiomas de Blum podem ser usados para definir classes de complexidade sem se referir a um modelo computacional concreto."@pt . . . "\u5728\u8A08\u7B97\u8907\u96DC\u5EA6\u7406\u8AD6\u4E2D\uFF0C\u4E00\u500B\u8907\u96DC\u5EA6\u985E\u6307\u7684\u662F\u4E00\u7FA4\u8907\u96DC\u5EA6\u985E\u4F3C\u7684\u554F\u984C\u7684\u96C6\u5408\u3002\u4E00\u500B\u5178\u578B\u7684\u8907\u96DC\u5EA6\u985E\u7684\u5B9A\u7FA9\u6709\u4EE5\u4E0B\u5F62\u5F0F\uFF1A \u53EF\u4EE5\u88AB\u540C\u4E00\u500B\u62BD\u8C61\u6A5F\u5668M\u4F7F\u7528O(f(n))\u7684\u8CC7\u6E90R\u6240\u89E3\u6C7A\u7684\u554F\u984C\u7684\u96C6\u5408\uFF08n\u662F\u8F38\u5165\u8CC7\u6599\u7684\u5927\u5C0F\uFF09\u3002 \u4F8B\u5982NP\u985E\u5225\u5C31\u662F\u4E00\u7FA4\u53EF\u4EE5\u88AB\u4E00\u975E\u78BA\u5B9A\u578B\u5716\u9748\u6A5F\u4EE5\u591A\u9805\u5F0F\u6642\u9593\u89E3\u6C7A\u7684\u6C7A\u5B9A\u578B\u554F\u984C\u3002\u800CP\u985E\u5225\u5247\u662F\u4E00\u7FA4\u53EF\u4EE5\u88AB\u78BA\u5B9A\u578B\u5716\u9748\u6A5F\u4EE5\u591A\u9805\u5F0F\u6642\u9593\u89E3\u6C7A\u7684\u6C7A\u5B9A\u578B\u554F\u984C\u3002\u67D0\u4E9B\u8907\u96DC\u5EA6\u985E\u662F\u4E00\u7FA4\u51FD\u5F0F\u554F\u984C\u7684\u96C6\u5408\uFF0C\u4F8B\u5982\u3002 \u8A31\u591A\u8907\u96DC\u5EA6\u985E\u53EF\u70BA\u6578\u5B78\u908F\u8F2F\u6240\u63CF\u8FF0\u523B\u5283\uFF0C\u8ACB\u898B\u3002 \u5E03\u76E7\u59C6\u8907\u96DC\u5EA6\u5247\u4E0D\u9700\u5BE6\u969B\u62BD\u8C61\u6A5F\u5668\u5C31\u53EF\u5B9A\u7FA9\u8907\u96DC\u5EA6\u985E\u3002"@zh . . . . . "Classe de complexidade"@pt . . "Nella teoria della complessit\u00E0 computazionale, una classe di complessit\u00E0 \u00E8 un insieme di problemi di una certa complessit\u00E0. Un esempio tipico di definizione di classe di complessit\u00E0 ha la forma: l'insieme di problemi che, se esiste la soluzione, possono essere risolti da una macchina astratta M usando della risorsa R, con dimensione dell'input Ad esempio, la classe NP \u00E8 l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, mentre la classe P \u00E8 l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale. Alcune classi di complessit\u00E0 sono insiemi di problemi costruttivi (cio\u00E8 che richiedono di calcolare una funzione, e non di rispondere S\u00CC o NO), come ad esempio . Molte classi di complessit\u00E0 possono essere caratterizzate in termini della logica matematica necessaria ad esprimerle; vedi . Gli possono essere usati per definire classi di complessit\u00E0 senza riferirsi ad un concreto."@it . "Classe de complexit\u00E9"@fr . "In der Komplexit\u00E4tstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bez\u00FCglich einer bestimmten Ressource, meist bez\u00FCglich des Zeitaufwands oder des (Speicher-)Platzaufwands. Bei Problemen wird dabei stets das \u201Ekosteng\u00FCnstigste\u201C L\u00F6sungsverfahren angenommen. Der Aufwand ist im Allgemeinen abh\u00E4ngig von der \u201EGr\u00F6\u00DFe\u201C der Eingabe, wie viele Elemente sie umfasst. Abgesch\u00E4tzt wird der asymptotische Aufwand, also f\u00FCr sehr viele Eingabeelemente. Dabei zeigt sich, dass die Probleme bzgl. ihres Aufwands Gruppen bilden, deren Aufwand f\u00FCr gro\u00DFe Eingabemengen auf \u00E4hnliche Weise anw\u00E4chst; diese Gruppen werden Komplexit\u00E4tsklassen genannt. Eine Komplexit\u00E4tsklasse ist eine Menge von Problemen, welche sich in einem bestimmten ressourcenbeschr\u00E4nkten Berechnungsmodell berechnen lassen. Definiert wird eine Komplexit\u00E4tsklasse durch eine obere Schranke f\u00FCr den Bedarf einer bestimmten Ressource unter Voraussetzung eines Berechnungsmodells. Die am h\u00E4ufigsten betrachteten Ressourcen sind die Anzahl der notwendigen Berechnungsschritte zur L\u00F6sung eines Problems (Zeitkomplexit\u00E4t) oder der Bedarf an Speicherplatz (Raum- oder Platzkomplexit\u00E4t). Gemessen wird der Ressourcenbedarf in der Regel durch sein asymptotisches Verhalten an der Obergrenze (dem worst case) in Abh\u00E4ngigkeit von der L\u00E4nge der Eingabe (Problemgr\u00F6\u00DFe). Auch andere Ma\u00DFe des Ressourcenbedarfs sind m\u00F6glich, etwa der statistische Mittelwert \u00FCber alle m\u00F6glichen Eingaben. Dieses Ma\u00DF ist jedoch formal nur schwer zu analysieren. Da durch eine Komplexit\u00E4tsklasse nur eine obere Grenze f\u00FCr den Ressourcenbedarf festgelegt ist, wird somit f\u00FCr ein gegebenes Berechnungsmodell eine Hierarchie von Komplexit\u00E4tsklassen gebildet, wobei weniger m\u00E4chtige Klassen jeweils vollst\u00E4ndig in den jeweils h\u00F6heren Komplexit\u00E4tsklassen enthalten sind. Zudem k\u00F6nnen durch formale Methoden auch \u00FCber unterschiedliche Berechnungsmodelle oder Ressourcen definierte Klassen zueinander in Bezug gesetzt werden."@de . . "\u8907\u96D1\u6027\u30AF\u30E9\u30B9\uFF08\u3075\u304F\u3056\u3064\u305B\u3044\u30AF\u30E9\u30B9\u3001\u82F1: Complexity class\uFF09\u306F\u3001\u8A08\u7B97\u8907\u96D1\u6027\u7406\u8AD6\u306B\u304A\u3044\u3066\u95A2\u9023\u3059\u308B\u8907\u96D1\u6027\u306E\u554F\u984C\u306E\u96C6\u5408\u3092\u6307\u3059\u3002\u5178\u578B\u7684\u306A\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u306F\u4EE5\u4E0B\u306E\u3088\u3046\u306B\u5B9A\u7FA9\u3055\u308C\u308B\u3002 \u62BD\u8C61\u6A5F\u68B0 M \u306B\u3088\u308AO(f(n))\u306E\u8A08\u7B97\u8CC7\u6E90 R \u3092\u4F7F\u3063\u3066\u89E3\u304F\u4E8B\u304C\u51FA\u6765\u308B\u554F\u984C\u306E\u96C6\u5408\uFF08n\u306F\u5165\u529B\u9577\uFF09 \u4F8B\u3048\u3070\u3001\u30AF\u30E9\u30B9NP\u306F\u975E\u6C7A\u5B9A\u6027\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u30DE\u30B7\u30F3\u3067\u591A\u9805\u5F0F\u6642\u9593\u3067\u89E3\u304F\u4E8B\u304C\u51FA\u6765\u308B\u6C7A\u5B9A\u554F\u984C\u306E\u96C6\u5408\u3067\u3042\u308B\u3002\u307E\u305F\u3001\u30AF\u30E9\u30B9PSPACE\u306F\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u30DE\u30B7\u30F3\u3067\u3067\u89E3\u304F\u4E8B\u304C\u51FA\u6765\u308B\u6C7A\u5B9A\u554F\u984C\u306E\u96C6\u5408\u3067\u3042\u308B\u3002\u3053\u3053\u3067\u3001\u9818\u57DF\u3068\u306F\u3001\u5B9F\u4E16\u754C\u3067\u306F\u30E1\u30E2\u30EA\u7A7A\u9593\u3001\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u30DE\u30B7\u30F3\u3067\u306F\u30C6\u30FC\u30D7\u306E\u9577\u3055\u3068\u8003\u3048\u308C\u3070\u3088\u3044\u3002\u4E00\u90E8\u306E\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u306F\u51FD\u6570\u554F\u984C\u306E\u96C6\u5408\u3067\u3042\u308B\uFF08\u4F8B\u3048\u3070\uFF09\u3002 \u6570\u7406\u8AD6\u7406\u5B66\u3067\u306F\u8868\u73FE\u306E\u5FC5\u8981\u306B\u5FDC\u3058\u3066\u591A\u6570\u306E\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u304C\u5B9A\u7FA9\u3055\u308C\u308B\uFF08\u8A18\u8FF0\u8A08\u7B97\u91CF\uFF09\u3002 \u30D6\u30E9\u30E0\u306E\u516C\u7406\u3092\u4F7F\u3046\u3068\u3001\u5B8C\u5168\u306A\u8A08\u7B97\u6A21\u578B\u3092\u53C2\u7167\u3057\u306A\u304F\u3068\u3082\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u3092\u5B9A\u7FA9\u3067\u304D\u308B\u3002"@ja . . . "1122036777"^^ . . . . . "Clase de complejidad"@es . . . . . . . . . . . "En teor\u00EDa de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisi\u00F3n de complejidad relacionada. Una clase de complejidad tiene una definici\u00F3n de la forma:"@es . . . . . . . . . . . . . . "2019-08-27"^^ . . . . "De complexiteitsgraad van een bepaald algoritme is de manier waarop dat algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt."@nl . . "\uBCF5\uC7A1\uB3C4 \uC885\uB958(\u8907\u96DC\u5EA6 \u7A2E\u985E)\uB294 \uACC4\uC0B0 \uBCF5\uC7A1\uB3C4 \uC774\uB860\uC5D0\uC11C \uC5D0 \uB530\uB77C\uC11C \uBB38\uC81C\uB97C \uBD84\uB958\uD55C \uAC83\uC774\uB2E4. \uBCF5\uC7A1\uB3C4 \uC885\uB958\uC758 \uC77C\uBC18\uC801 \uC815\uC758\uB294 \uB2E4\uC74C\uACFC \uAC19\uC740 \uD615\uD0DC\uB85C \uB418\uC5B4 \uC788\uB2E4. \uC608\uB97C \uB4E4\uC5B4, NP\uB294 \uD655\uB960\uC801 \uD29C\uB9C1 \uAE30\uACC4\uAC00 \uB2E4\uD56D\uC2DC\uAC04\uC5D0 \uD480 \uC218 \uC788\uB294 \uD310\uC815 \uBB38\uC81C\uC758 \uC9D1\uD569\uC774\uACE0 PSPACE\uB294 \uACB0\uC815\uB860\uC801 \uD29C\uB9C1 \uAE30\uACC4\uAC00 \uB2E4\uD56D\uACF5\uAC04\uC5D0 \uD480 \uC218 \uC788\uB294 \uD310\uC815 \uBB38\uC81C\uC758 \uC9D1\uD569\uC774\uB2E4. \uD568\uC218 \uBB38\uC81C\uC758 \uC9D1\uD569\uC778 \uAC19\uC740 \uAC83\uB3C4 \uC788\uB2E4. \uAD6C\uCCB4\uC801\uC778 \uC5C6\uC774 \uBCF5\uC7A1\uB3C4 \uC885\uB958\uB97C \uC815\uC758\uD558\uB294 \uB370 \uC0AC\uC6A9\uD560 \uC218 \uC788\uB294 \uB3C4 \uC788\uB2E4."@ko . . "Klasa z\u0142o\u017Cono\u015Bci \u2013 zbi\u00F3r problem\u00F3w obliczeniowych o podobnej z\u0142o\u017Cono\u015Bci obliczeniowej. Najbardziej pospolit\u0105 definicj\u0105 klasy z\u0142o\u017Cono\u015Bci jest: Zbi\u00F3r problem\u00F3w, kt\u00F3re mog\u0105 by\u0107 rozwi\u0105zane na M przy u\u017Cyciu O(f(n)) zasobu R, gdzie n jest rozmiarem wej\u015Bcia. Na przyk\u0142ad klasa P to zbi\u00F3r problem\u00F3w decyzyjnych, kt\u00F3re mo\u017Cna rozwi\u0105za\u0107 na maszynie Turinga w czasie wielomianowym natomiast klasa NP to zbi\u00F3r problem\u00F3w decyzyjnych, kt\u00F3re mo\u017Cna rozwi\u0105za\u0107 na niedeterministycznej maszynie Turinga w czasie wielomianowym."@pl . . . . . . . . . . . . . . . . . "502426"^^ . . . . . . . . . . . . . "Komplexit\u00E4tsklasse"@de . . . . . "\uBCF5\uC7A1\uB3C4 \uC885\uB958(\u8907\u96DC\u5EA6 \u7A2E\u985E)\uB294 \uACC4\uC0B0 \uBCF5\uC7A1\uB3C4 \uC774\uB860\uC5D0\uC11C \uC5D0 \uB530\uB77C\uC11C \uBB38\uC81C\uB97C \uBD84\uB958\uD55C \uAC83\uC774\uB2E4. \uBCF5\uC7A1\uB3C4 \uC885\uB958\uC758 \uC77C\uBC18\uC801 \uC815\uC758\uB294 \uB2E4\uC74C\uACFC \uAC19\uC740 \uD615\uD0DC\uB85C \uB418\uC5B4 \uC788\uB2E4. \uC608\uB97C \uB4E4\uC5B4, NP\uB294 \uD655\uB960\uC801 \uD29C\uB9C1 \uAE30\uACC4\uAC00 \uB2E4\uD56D\uC2DC\uAC04\uC5D0 \uD480 \uC218 \uC788\uB294 \uD310\uC815 \uBB38\uC81C\uC758 \uC9D1\uD569\uC774\uACE0 PSPACE\uB294 \uACB0\uC815\uB860\uC801 \uD29C\uB9C1 \uAE30\uACC4\uAC00 \uB2E4\uD56D\uACF5\uAC04\uC5D0 \uD480 \uC218 \uC788\uB294 \uD310\uC815 \uBB38\uC81C\uC758 \uC9D1\uD569\uC774\uB2E4. \uD568\uC218 \uBB38\uC81C\uC758 \uC9D1\uD569\uC778 \uAC19\uC740 \uAC83\uB3C4 \uC788\uB2E4. \uAD6C\uCCB4\uC801\uC778 \uC5C6\uC774 \uBCF5\uC7A1\uB3C4 \uC885\uB958\uB97C \uC815\uC758\uD558\uB294 \uB370 \uC0AC\uC6A9\uD560 \uC218 \uC788\uB294 \uB3C4 \uC788\uB2E4."@ko . . . "\u8907\u96D1\u6027\u30AF\u30E9\u30B9\uFF08\u3075\u304F\u3056\u3064\u305B\u3044\u30AF\u30E9\u30B9\u3001\u82F1: Complexity class\uFF09\u306F\u3001\u8A08\u7B97\u8907\u96D1\u6027\u7406\u8AD6\u306B\u304A\u3044\u3066\u95A2\u9023\u3059\u308B\u8907\u96D1\u6027\u306E\u554F\u984C\u306E\u96C6\u5408\u3092\u6307\u3059\u3002\u5178\u578B\u7684\u306A\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u306F\u4EE5\u4E0B\u306E\u3088\u3046\u306B\u5B9A\u7FA9\u3055\u308C\u308B\u3002 \u62BD\u8C61\u6A5F\u68B0 M \u306B\u3088\u308AO(f(n))\u306E\u8A08\u7B97\u8CC7\u6E90 R \u3092\u4F7F\u3063\u3066\u89E3\u304F\u4E8B\u304C\u51FA\u6765\u308B\u554F\u984C\u306E\u96C6\u5408\uFF08n\u306F\u5165\u529B\u9577\uFF09 \u4F8B\u3048\u3070\u3001\u30AF\u30E9\u30B9NP\u306F\u975E\u6C7A\u5B9A\u6027\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u30DE\u30B7\u30F3\u3067\u591A\u9805\u5F0F\u6642\u9593\u3067\u89E3\u304F\u4E8B\u304C\u51FA\u6765\u308B\u6C7A\u5B9A\u554F\u984C\u306E\u96C6\u5408\u3067\u3042\u308B\u3002\u307E\u305F\u3001\u30AF\u30E9\u30B9PSPACE\u306F\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u30DE\u30B7\u30F3\u3067\u3067\u89E3\u304F\u4E8B\u304C\u51FA\u6765\u308B\u6C7A\u5B9A\u554F\u984C\u306E\u96C6\u5408\u3067\u3042\u308B\u3002\u3053\u3053\u3067\u3001\u9818\u57DF\u3068\u306F\u3001\u5B9F\u4E16\u754C\u3067\u306F\u30E1\u30E2\u30EA\u7A7A\u9593\u3001\u30C1\u30E5\u30FC\u30EA\u30F3\u30B0\u30DE\u30B7\u30F3\u3067\u306F\u30C6\u30FC\u30D7\u306E\u9577\u3055\u3068\u8003\u3048\u308C\u3070\u3088\u3044\u3002\u4E00\u90E8\u306E\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u306F\u51FD\u6570\u554F\u984C\u306E\u96C6\u5408\u3067\u3042\u308B\uFF08\u4F8B\u3048\u3070\uFF09\u3002 \u6570\u7406\u8AD6\u7406\u5B66\u3067\u306F\u8868\u73FE\u306E\u5FC5\u8981\u306B\u5FDC\u3058\u3066\u591A\u6570\u306E\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u304C\u5B9A\u7FA9\u3055\u308C\u308B\uFF08\u8A18\u8FF0\u8A08\u7B97\u91CF\uFF09\u3002 \u30D6\u30E9\u30E0\u306E\u516C\u7406\u3092\u4F7F\u3046\u3068\u3001\u5B8C\u5168\u306A\u8A08\u7B97\u6A21\u578B\u3092\u53C2\u7167\u3057\u306A\u304F\u3068\u3082\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u3092\u5B9A\u7FA9\u3067\u304D\u308B\u3002"@ja . . . "\u8907\u96D1\u6027\u30AF\u30E9\u30B9"@ja . "En informatique th\u00E9orique, et plus pr\u00E9cis\u00E9ment en th\u00E9orie de la complexit\u00E9, une classe de complexit\u00E9 est un ensemble de probl\u00E8mes algorithmiques dont la r\u00E9solution n\u00E9cessite la m\u00EAme quantit\u00E9 d'une certaine ressource. Une classe est souvent d\u00E9finie comme l'ensemble de tous les probl\u00E8mes qui peuvent \u00EAtre r\u00E9solus sur un mod\u00E8le de calcul M, utilisant une quantit\u00E9 de ressources du type R, o\u00F9 n, est la taille de l'entr\u00E9e. Les classes les plus usuelles sont celles d\u00E9finies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace. On peut par exemple citer les classes P et NP."@fr . . . . . . . . . . . . . . "Klasa z\u0142o\u017Cono\u015Bci \u2013 zbi\u00F3r problem\u00F3w obliczeniowych o podobnej z\u0142o\u017Cono\u015Bci obliczeniowej. Najbardziej pospolit\u0105 definicj\u0105 klasy z\u0142o\u017Cono\u015Bci jest: Zbi\u00F3r problem\u00F3w, kt\u00F3re mog\u0105 by\u0107 rozwi\u0105zane na M przy u\u017Cyciu O(f(n)) zasobu R, gdzie n jest rozmiarem wej\u015Bcia. Na przyk\u0142ad klasa P to zbi\u00F3r problem\u00F3w decyzyjnych, kt\u00F3re mo\u017Cna rozwi\u0105za\u0107 na maszynie Turinga w czasie wielomianowym natomiast klasa NP to zbi\u00F3r problem\u00F3w decyzyjnych, kt\u00F3re mo\u017Cna rozwi\u0105za\u0107 na niedeterministycznej maszynie Turinga w czasie wielomianowym. Z kolei klasa to zbi\u00F3r problem\u00F3w decyzyjnych, kt\u00F3re mo\u017Cna rozwi\u0105za\u0107 na r\u00F3wnoleg\u0142ej maszynie RAM w czasie polilogarytmicznym przy u\u017Cyciu wielomianowej liczby procesor\u00F3w, a to klasa problem\u00F3w, dla kt\u00F3rych istnieje dzia\u0142aj\u0105ca w czasie wielomianowym, kt\u00F3ra zwraca \u201Enie\u201D zawsze, kiedy prawid\u0142ow\u0105 odpowiedzi\u0105 jest \u201Enie\u201D, i zwraca \u201Etak\u201D (z prawdopodobie\u0144stwem, kt\u00F3re dla \u017Cadnych danych nie spada poni\u017Cej pewnej warto\u015Bci) lub \u201Enie\u201D, kiedy prawid\u0142ow\u0105 odpowiedzi\u0105 jest \u201Etak\u201D"@pl . . . . . . .