| dbo:abstract
|
- Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs". Generic-case complexity is a way of measuring the complexity of a computational problem by neglecting a small set ofunrepresentative inputs and considering worst-case complexity on the rest.Small is defined in terms of asymptotic density.The apparent efficacy of generic case complexity is because for a wide variety of concrete computational problems, the most difficult instances seem to be rare. Typical instances are relatively easy. This approach to complexity originated in combinatorial group theory, which has a computational tradition going back to the beginning of the last century.The notion of generic complexity was introduced in a 2003 paper, where authors showed that for a large class of finitely generated groups the generic time complexity of some classical decision problems from combinatorial group theory, namely the word problem, conjugacy problem and , are linear. A detailed introduction of generic case complexity can be found in the surveys. (en)
- La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles. Cette approche de la complexité prend son origine dans la théorie combinatoire des groupes qui a une tradition dans l'étude de problèmes algorithmiques qui remonte au début du XXe siècle. La notion de complexité générique a été introduit en 2003 dans des articles de Kapovich, Miasnikov, Schupp et Shpilrain. Les auteurs montrent que, pour une large classe de groupes finiment engendrés, la complexité générique de quelques problèmes de décision classiques de la théorie combinatoire des groupes, à savoir le problème du mot, le (en), ou le problème d'appartenance, est en fait linéaire. Une introduction et un survol de la complexité générique sont donnés dans un texte de R. Gilman, A. G. Miasnikov, A. D. Myasnikov, et A. Ushakov. Les livres de Miasnikov, Shpilrain et Ushakov traitent principalement des résultats des auteurs relativement à la cryptographie. (fr)
- Complexidade de Caso Genérico é uma subárea da teoria da complexidade computacional que estuda a complexidade de problemas computacionais na "maioria das entradas". Complexidade de Caso Genérico é uma forma de medir a complexidade de um problema computacional desprezando um pequeno conjunto de entradas não representativas e aplicando a complexidade do pior caso nas entradas restantes.Pequeno é definido em termos de densidade assintótica.A aparente eficácia da complexidade de caso genérico se dá porque, para uma ampla variedade de problemas computacionais concretos, as instâncias mais difíceis parecem ser raras. Os casos típicos, são relativamente fáceis. Esta abordagem da complexidade foi originada em teoria combinatória dos grupos, que tem uma tradição computacional que remonta ao início do século passado.A noção de complexidade genérica foi introduzida em um artigo de 2003 onde os autores mostraram que, para uma grande classe de grupos gerados finitamente a complexidade de tempo genérica de alguns problemas clássicos de decisão provenientes da teoria combinatória dos grupos, conhecidamente, o problema da aceitação de uma palavra, problema da conjugação e o problema da pertinência, são lineares. Uma introdução detalhada da complexidade de caso genérico pode ser encontrado nas pesquisas. (pt)
|
| rdfs:comment
|
- Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs". Generic-case complexity is a way of measuring the complexity of a computational problem by neglecting a small set ofunrepresentative inputs and considering worst-case complexity on the rest.Small is defined in terms of asymptotic density.The apparent efficacy of generic case complexity is because for a wide variety of concrete computational problems, the most difficult instances seem to be rare. Typical instances are relatively easy. (en)
- La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles. (fr)
- Complexidade de Caso Genérico é uma subárea da teoria da complexidade computacional que estuda a complexidade de problemas computacionais na "maioria das entradas". Complexidade de Caso Genérico é uma forma de medir a complexidade de um problema computacional desprezando um pequeno conjunto de entradas não representativas e aplicando a complexidade do pior caso nas entradas restantes.Pequeno é definido em termos de densidade assintótica.A aparente eficácia da complexidade de caso genérico se dá porque, para uma ampla variedade de problemas computacionais concretos, as instâncias mais difíceis parecem ser raras. Os casos típicos, são relativamente fáceis. (pt)
|
