. "Langage creux"@fr . . . . "\u5728\u8A08\u7B97\u8907\u96DC\u6027\u7406\u8AD6\u88E1\u9762, \u7A00\u758F\u8A9E\u8A00\u662F\u4E00\u7A2E\u5F62\u5F0F\u8A9E\u8A00 (\u4E00\u5806\u5B57\u4E32\u7684\u96C6\u5408\u5B57\u4E32)\uFF0C\u4E26\u4E14\u9019\u8A9E\u8A00\u5167\u9577\u5EA6\u70BAn\u7684\u5B57\u4E32\u500B\u6578\uFF0C\u88AB\u4E00\u500Bn\u7684\u591A\u9805\u5F0F\u6240\u9650\u5236\u4F4F\u3002 \u9019\u7A2E\u8A9E\u8A00\u4E3B\u8981\u88AB\u7528\u4F86\u7814\u7A76NP\u9019\u985E\u8A9E\u8A00\u8207\u5176\u4ED6\u7A2E\u985E\u8A9E\u8A00\u7684\u95DC\u4FC2\u3002\u5305\u542B\u6240\u6709\u7A00\u758F\u8A9E\u8A00\u7684\u8907\u96DC\u5EA6\u985E\u88AB\u7A31\u4F5CSPARSE\u3002 \u7A00\u758F\u8A9E\u8A00\u6703\u88AB\u53EB\u505A\u7A00\u758F\u7684\u539F\u56E0\u662F\u56E0\u70BA\uFF0C\u5C0D\u4EFB\u4F55\u8A9E\u8A00\uFF0C\u9577\u5EA6\u70BAn\u7684\u5B57\u4E32\u53EF\u80FD\u6027\u500B\u6578\u7E3D\u5171\u67092n\u500B\uFF0C\u800C\u5982\u679C\u67D0\u7279\u5B9A\u8A9E\u8A00\u53EA\u6709\u5305\u542B\u9019\u4E00\u4E9B\u5B57\u4E32\u88E1\u9762\u7684\u591A\u9805\u5F0F\u500B\u6578\u500B\uFF0C\u90A3\u9019\u8A9E\u8A00\u6240\u5305\u542B\u5B57\u4E32\u7684\u6BD4\u4F8B\u6703\u96A8\u8457n\u7684\u6210\u9577\u5F88\u5FEB\u7684\u6E1B\u5C11\u3002 \u6240\u6709\u4E00\u5143\u8A9E\u8A00\u90FD\u662F\u7A00\u758F\u8A9E\u8A00\u3002\u4E00\u500B\u7A00\u758F\u8A9E\u8A00\u6BD4\u8F03\u4E0D\u55AE\u7D14\u7684\u4F8B\u5B50\u662F\uFF0C\u67D0\u500B\u8A9E\u8A00\u5305\u542B\u6240\u6709\u6070\u6709k\u500B1(k\u662F\u67D0\u500B\u5E38\u6578)\u7684\u4E8C\u9032\u4F4D\u5B57\u4E32\uFF0C; \u5C0D\u4EFB\u4F55\u9577\u5EA6n, \u9019\u500B\u8A9E\u8A00\u50C5\u5305\u542B\u500B\u5B57\u4E32, \u800C\u9019\u500B\u6578\u5B57\u5247\u88AB nk\u7D66\u9650\u5236\u4F4F\u3002"@zh . . "Em teoria da complexidade computacional, uma linguagem esparsa \u00E9 uma linguagem formal (um conjunto de strings) cujo n\u00FAmero de strings de comprimento n na l\u00EDngua \u00E9 limitada por uma fun\u00E7\u00E3o de polin\u00F4mio n. S\u00E3o utilizadas principalmente no estudo da rela\u00E7\u00E3o entre a classe de complexidade NP com outras classes. A classe de complexidade de todas as l\u00EDnguas esparsas s\u00E3o chamadas de SPARSE."@pt . "In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes. The complexity class of all sparse languages is called SPARSE."@en . . . "Linguagem esparsa"@pt . . . . "1118453397"^^ . "En th\u00E9orie de la complexit\u00E9, un langage creux est un langage o\u00F9 le nombre de mots de longueur n est born\u00E9 par un polyn\u00F4me en n. Ils sont utiles dans l'\u00E9tude de la classe NP. L'adjectif creux illustre bien un tel langage : sur un alphabet \u00E0 deux lettres, comme il y a 2 n mots de longueur n, alors s'il n'y a qu'un nombre polynomial de mots de longueur n, cela signifie que la proportion de mots de longueur n dans un langage creux tend vers 0, quand n tend vers l'infini."@fr . . . . . . . . . . . . . . "12769596"^^ . "En th\u00E9orie de la complexit\u00E9, un langage creux est un langage o\u00F9 le nombre de mots de longueur n est born\u00E9 par un polyn\u00F4me en n. Ils sont utiles dans l'\u00E9tude de la classe NP. L'adjectif creux illustre bien un tel langage : sur un alphabet \u00E0 deux lettres, comme il y a 2 n mots de longueur n, alors s'il n'y a qu'un nombre polynomial de mots de longueur n, cela signifie que la proportion de mots de longueur n dans un langage creux tend vers 0, quand n tend vers l'infini."@fr . . "\u5728\u8A08\u7B97\u8907\u96DC\u6027\u7406\u8AD6\u88E1\u9762, \u7A00\u758F\u8A9E\u8A00\u662F\u4E00\u7A2E\u5F62\u5F0F\u8A9E\u8A00 (\u4E00\u5806\u5B57\u4E32\u7684\u96C6\u5408\u5B57\u4E32)\uFF0C\u4E26\u4E14\u9019\u8A9E\u8A00\u5167\u9577\u5EA6\u70BAn\u7684\u5B57\u4E32\u500B\u6578\uFF0C\u88AB\u4E00\u500Bn\u7684\u591A\u9805\u5F0F\u6240\u9650\u5236\u4F4F\u3002 \u9019\u7A2E\u8A9E\u8A00\u4E3B\u8981\u88AB\u7528\u4F86\u7814\u7A76NP\u9019\u985E\u8A9E\u8A00\u8207\u5176\u4ED6\u7A2E\u985E\u8A9E\u8A00\u7684\u95DC\u4FC2\u3002\u5305\u542B\u6240\u6709\u7A00\u758F\u8A9E\u8A00\u7684\u8907\u96DC\u5EA6\u985E\u88AB\u7A31\u4F5CSPARSE\u3002 \u7A00\u758F\u8A9E\u8A00\u6703\u88AB\u53EB\u505A\u7A00\u758F\u7684\u539F\u56E0\u662F\u56E0\u70BA\uFF0C\u5C0D\u4EFB\u4F55\u8A9E\u8A00\uFF0C\u9577\u5EA6\u70BAn\u7684\u5B57\u4E32\u53EF\u80FD\u6027\u500B\u6578\u7E3D\u5171\u67092n\u500B\uFF0C\u800C\u5982\u679C\u67D0\u7279\u5B9A\u8A9E\u8A00\u53EA\u6709\u5305\u542B\u9019\u4E00\u4E9B\u5B57\u4E32\u88E1\u9762\u7684\u591A\u9805\u5F0F\u500B\u6578\u500B\uFF0C\u90A3\u9019\u8A9E\u8A00\u6240\u5305\u542B\u5B57\u4E32\u7684\u6BD4\u4F8B\u6703\u96A8\u8457n\u7684\u6210\u9577\u5F88\u5FEB\u7684\u6E1B\u5C11\u3002 \u6240\u6709\u4E00\u5143\u8A9E\u8A00\u90FD\u662F\u7A00\u758F\u8A9E\u8A00\u3002\u4E00\u500B\u7A00\u758F\u8A9E\u8A00\u6BD4\u8F03\u4E0D\u55AE\u7D14\u7684\u4F8B\u5B50\u662F\uFF0C\u67D0\u500B\u8A9E\u8A00\u5305\u542B\u6240\u6709\u6070\u6709k\u500B1(k\u662F\u67D0\u500B\u5E38\u6578)\u7684\u4E8C\u9032\u4F4D\u5B57\u4E32\uFF0C; \u5C0D\u4EFB\u4F55\u9577\u5EA6n, \u9019\u500B\u8A9E\u8A00\u50C5\u5305\u542B\u500B\u5B57\u4E32, \u800C\u9019\u500B\u6578\u5B57\u5247\u88AB nk\u7D66\u9650\u5236\u4F4F\u3002"@zh . . . . . . . . "\u7A00\u758F\u8A9E\u8A00"@zh . . . "Em teoria da complexidade computacional, uma linguagem esparsa \u00E9 uma linguagem formal (um conjunto de strings) cujo n\u00FAmero de strings de comprimento n na l\u00EDngua \u00E9 limitada por uma fun\u00E7\u00E3o de polin\u00F4mio n. S\u00E3o utilizadas principalmente no estudo da rela\u00E7\u00E3o entre a classe de complexidade NP com outras classes. A classe de complexidade de todas as l\u00EDnguas esparsas s\u00E3o chamadas de SPARSE. As linguagens esparsas s\u00E3o chamados de \"esparsas\", porque h\u00E1 um total de 2n strings de comprimento n, e se uma linguagem s\u00F3 cont\u00E9m polinomialmente muitos destes, ent\u00E3o a propor\u00E7\u00E3o de cadeias de comprimento n que cont\u00E9m rapidamente vai de zero quanto a medida que n crescer. Todos linguagens un\u00E1rias s\u00E3o esparsas. Um exemplo de uma linguagem esparsa n\u00E3o trivial \u00E9 o conjunto de cadeias bin\u00E1rias contendo exatamente k 1 bits para alguns k fixos; para cada n, h\u00E1 apenas strings na linguagem, que \u00E9 delimitada por nk."@pt . . . . . . "Sparse language"@en . . . . . . . "4553"^^ . . "In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes. The complexity class of all sparse languages is called SPARSE. Sparse languages are called sparse because there are a total of 2n strings of length n, and if a language only contains polynomially many of these, then the proportion of strings of length n that it contains rapidly goes to zero as n grows. All unary languages are sparse. An example of a nontrivial sparse language is the set of binary strings containing exactly k 1 bits for some fixed k; for each n, there are only strings in the language, which is bounded by nk."@en . .