• [^] # Re: Que ne savons-nous pas ?

    Posté par (site web personnel) . En réponse au journal Que ne savons-nous pas ?. Évalué à 1.

    P = NP ne peut pas être "indécidable". Ca n'a pas de sens.

    Le mot "indécidable" en informatique se rapporte à un "problème", et un "problème" est une question dont la réponse dépends des données en entrée. C'est en gros une fonction de E dans {0,1}, ou E est un ensemble.

    Si E est fini, alors le problème est décidable. L'algo qui donne la réponse étant

    switch(x) {
    case ...:
    case ...:
    ...
    return true;
    break;
    default:
    return false;
    }

    Dans le cas P = NP, il n'y a pas d'entrée, donc, l'algorithme qui décide le problème "P = NP" est tout simplement

    return true;

    Ou alors

    return false;

    Le truc, c'est qu'on ne sait pas lequel des algo est bon, mais on sait qu'il en existe un.

    Ce qui est peut-être possible, c'est que P=NP ne soit pas *prouvable* dans une logique donnée.