Et si l'humain arrivait à simuler un Bot !

[invite765732342432]

Intéressant. Cela ne me semble pas évident, mais pourquoi pas...

Note: Pour moi un cafard est conscient.

Autre point : si on admet l'ordre que tu indiques, alors il n'existe pas de preuve qu'il soit possible de faire un bot intelligent mais non conscient, ni même de bot intelligent qui ne soit pas émotif.

Il n'existe aucune preuve d'aucune sorte concernant la possibilité ou l'impossibilité de faire ces choses là.
Ne t'attarde pas trop sur l'ordre que j'ai donné, il n'est qu'un exemple à la louche. Une réponse précise nécessiterait une étude de plusieurs années, et encore la conclusion serait encore bien fragile

Voilà pourquoi je n'accepte pas les propos catégoriques qu'on trouve dans ce fil et les autres sur le même sujet.
-----

[invite6c250b59]

Alors je me demande comment on calcule la complexité de ce genre de choses...

Défini comme ça, je n'en ai aucune idée non plus.

Sauf erreur, un problème NP-complet classique est le voyageur de commerce, qui se résout très bien en temps polynomial avec un algo "probabiliste".

Oui. Non! Les algo utilisés ont tous les mêmes problèmes:
-limités à des bas n
-aucune garantie sur la précision
-ne marchent qu'avec certains "instances" dont les propriétés stats sont spéciales.

Puisqu'on est dans le forum ludique, autant dire qu'on peut résoudre les NP-complet puisque le sudoku est NP-complet et que j'ai réussi à résoudre celui-ci

http://xkcd.com/74/

Comme mes cours d'algo sont loin (et que de toute façon je n'y allais pas), pourrais-tu me rappeler la différence entre NP-difficile et NP-complet ?

Informellement, c'est la même chose. Techniquement, un problème est:
-NP s'il est au moins aussi facile que n'importe quel problème dans NP.
-NP-difficile s'il est au moins aussi difficile que n'importe quel problème dans NP
-NP-complet s'il est à la fois NP et NP-difficile.

"Avec l'expression "complètement calculable", je suis entièrement d'accord. Sauf que les "computationalistes mous", dont je pense faire partie, parlent plutôt de "comportement approximable avec une précision aussi grande que souhaité (mais non-parfaite)"

Il n'y a pas de distinction à faire. Si c'est approximable avec une précision arbitraire, c'est calculable point barre. Penrose ne s'enfarge pas du tout là-dessus. D'ailleurs il inclu sans état d'âme le chaos déterministe dans la liste des choses calculables.

[invite765732342432]

Défini comme ça, je n'en ai aucune idée non plus.

Il me semblait aussi que ce genre de situations était trop complexe pour les calculs classiques de complexité. Mais comme je l'ai dit, je n'étais pas ferru de cours d'algo...

Oui. Non! Les algo utilisés ont tous les mêmes problèmes:

Euh... tu est bien en train de dire que les algo génétiques, la méthode des fourmis sont mauvais pour résoudre le problème du voyageur de commerce ?

Ou un algo que je ne connaissais pas (ou que j'ai oublié), le 2-opt:

Le défi des 250 villes est résolu en moyenne en 4 minutes avec un temps record inférieur à la seconde
(...)
A titre d'exemple, pour essayer de traiter le problème des 13 509 communes de plus de 500 habitants des Etats-Unis, (...) voici ci-dessous le premier parcours obtenu (21 082 000 après 14 minutes de calcul). Au bout de 2 h 30, j'atteins 20 899 000 alors que le meilleur parcours possible mesure 19 947 008.

5% de marge par rapport à l'optimum en 14 minutes... je trouve ça plutôt pas mal !

Informellement, c'est la même chose. Techniquement, un problème est:
-NP s'il est au moins aussi facile que n'importe quel problème dans NP.
-NP-difficile s'il est au moins aussi difficile que n'importe quel problème dans NP
-NP-complet s'il est à la fois NP et NP-difficile.

Merci pour le rappel.

[invité576543]

5% de marge par rapport à l'optimum en 14 minutes... je trouve ça plutôt pas mal !

Certes, mais est-ce que cela n'est pas juste confirmer que "trouver l'optimum" et "trouver une solution à moins de 5% de l'optimum" sont deux problèmes différents?

(Tu pourras aussi remercier pour le rappel... Une réponse intéressante à étudier, d'ailleurs!)

[invite765732342432]

Certes, mais est-ce que cela n'est pas juste confirmer que "trouver l'optimum" et "trouver une solution à moins de 5% de l'optimum" sont deux problèmes différents?

Oui... ça s'appelle enfoncer une porte ouverte...
Pourquoi ?

[invite6c250b59]

Il me semblait aussi que ce genre de situations était trop complexe pour les calculs classiques de complexité.

Je pensais plutôt à "trop mal défini dans ton post".

Euh... tu est bien en train de dire que les algo génétiques, la méthode des fourmis sont mauvais pour résoudre le problème du voyageur de commerce ?

Absolument. Ou plutôt, qu'ils ne sont pas connus pour marcher en dehors de cas particuliers.

Certes, mais est-ce que cela n'est pas juste confirmer que "trouver l'optimum" et "trouver une solution à moins de 5% de l'optimum" sont deux problèmes différents?

C'est même pire que ça. Il s'agit de villes réelles dont on peut supposer qu'elles respectent certaines contraintes, la plus sévère étant que tout est connecté de proche en proche ou peu s'en faut. Cela fait que toute tentative qui respecte une connectivité locale est forcément proche de la solution -il suffit d'en prendre une au hasard!

Autrement dit, il y a confusion entre le (vrai) problème du voyageur de commerce et le sous-problème du voyageur de commerce entre villes connectées de proche en proche. Le premier est NP-complet, le deuxième est probablement dans P.

(ça fait plaisir de te croiser à nouveau)

[invite765732342432]

Il s'agit de villes réelles dont on peut supposer qu'elles respectent certaines contraintes, la plus sévère étant que tout est connecté de proche en proche ou peu s'en faut (...) Autrement dit, il y a confusion entre le (vrai) problème du voyageur de commerce et le sous-problème du voyageur de commerce entre villes connectées de proche en proche.

Le test fait avec le 2-opt ne s'est pas intéressé à l'infrastructure existante.

Et je rappelle que l'informatique est là pour régler des problèmes du quotidien, et pas les situations en pire cas.
Il me semble peu probable également que le langage ou le comportement animal soient systématiquement des solutions en pire cas.

Enfin, les algo G et autres algo classiques d'IA ont l'immense avantage de pouvoir être stoppés à tout moment et de fournir quand même une solution.

[JPL]

À votre avis cette discussion ne serait-elle pas mieux à sa place dans Débats scientifiques ?

[invitebd2b1648]

JPL sur un ton humoristique cette discussion se voulait
Mais étant détenteur de la force choisir je te laisserais !

@ +