Posté par Jux .
En réponse au journal CAPTCHA.
Évalué à 10.
Le hic, c'est qu'il est aussi extrêmement difficile pour un humain de trouver la solution optimale d'un problème NP-complet non-trivial (bonne chance pour résoudre un voyageur du commerce à 100 noeuds). Le problème fondamental, c'est qu'on utilise en général la notion de complexité algorithmique pour des problèmes sur lesquels les ordinateurs sont justement plus forts que les humains, parce que ce sont en général des algorithmes qui demandent "juste" des calculs. Et les ordinateurs sont très forts au calcul.
Par contre, le lien que tu donnes chez Microsoft demande de reconnaître des photos de chat. La difficulté du problème ne réside pas dans la complexité algorithmique, mais dans le fait qu'on ne connaît juste pas d'algorithme (même NP) qui permette d'approcher la capacité humaine à interpréter une image.
Je pense que si tu veux un CAPTCHA qui ne soit pas crackable automatiquement, il faut plutôt s'orienter sur des domaines où les ordinateurs sont mauvais (reconnaissance d'images, interprétation de texte, etc..).
# Mauvaise approche
Posté par Jux . En réponse au journal CAPTCHA. Évalué à 10.
Le hic, c'est qu'il est aussi extrêmement difficile pour un humain de trouver la solution optimale d'un problème NP-complet non-trivial (bonne chance pour résoudre un voyageur du commerce à 100 noeuds). Le problème fondamental, c'est qu'on utilise en général la notion de complexité algorithmique pour des problèmes sur lesquels les ordinateurs sont justement plus forts que les humains, parce que ce sont en général des algorithmes qui demandent "juste" des calculs. Et les ordinateurs sont très forts au calcul.
Par contre, le lien que tu donnes chez Microsoft demande de reconnaître des photos de chat. La difficulté du problème ne réside pas dans la complexité algorithmique, mais dans le fait qu'on ne connaît juste pas d'algorithme (même NP) qui permette d'approcher la capacité humaine à interpréter une image.
Je pense que si tu veux un CAPTCHA qui ne soit pas crackable automatiquement, il faut plutôt s'orienter sur des domaines où les ordinateurs sont mauvais (reconnaissance d'images, interprétation de texte, etc..).