URL: https://linuxfr.org/users/barmic/journaux/captcha Title: CAPTCHA Authors: barmic Date: 2011年07月03日T00:36:07+02:00 License: CC By-SA Tags: Score: 6 Je lisais cet article totalement bidon sur les CAPTCHAS : http://www.xmco.fr/article-captcha.html Quand j'ai eu une idée grâce à la question dans la conclusion (je présume que je ne suis pas le seul, mais je n'ai pas encore vu d'implémentation). La question c'est « Mais peut-on réellement imaginer un algorithme que seul un humain puisse résoudre ? » et la réponse est **oui**. Tout les problèmes informatique de la classe NPComplet sont très difficilement solvables par un ordinateur. Pour rappel les [[Problème_NP-complet]] sont des problèmes dont on peut vérifier si une solution au problème est valide ou non en un temps polynomiale et, on va dire, qui ressemble à un problème NP-Complet déjà existant (en fait on démontre qu'on peut les formuler sous la forme d'un problème déjà NPComplet). Grosso modo leur résolution par un ordinateur consiste à générer des solutions et à les vérifier (en "brute force"). C'est rapide (même si peu efficace) sur des petites entrées et plus le nombres de paramètres augmente, plus c'est long (en suivant une courbe exponentiellle, si je ne me trompe pas). Un certains nombres de problèmes NPComplet sont assez ludiques (la coloration d'un graphe, le voyageur de commerce, le problème du sac à dos, ...), mais je crains qu'il faille avoir des entrées un peu trop grandes (graphes trop grands, trop grand nombres d'items à mettre dans le sac, etc) pour que ça pose vraiment un problème pour une machine et pas un humain. Qu'en pensez-vous ? Pensez-vous que ce serais réalisable ? PS : J'ai testé ceci http://research.microsoft.com/en-us/um/redmond/projects/asirra/ qui nous vient de chez Microsoft. Ça me semble pas mal surtout si on choisit un ensemble d'image assez embêtant (qu'il ne puisse pas trop se baser sur les couleurs, les formes ou les motifs).