problème 3-SAT
Répondre à la discussion
Affichage des résultats 1 à 6 sur 6

problème 3-SAT



  1. 15/05/2009, 14h10 #1
    invitedf72ed21

    problème 3-SAT


    ------

    Bonjour à tous,

    quelqu'un peut-il me dire si il existe une borne inférieure en temps pour le problème 3-SATsvp ? Ou si rien n'a encore été démontré ?

    Merci !
    David

    -----
  2. 15/05/2009, 14h46 #2
    Médiat

    Re : problème 3-SAT

    Citation Envoyé par daviddit Voir le message
    Bonjour à tous,

    quelqu'un peut-il me dire si il existe une borne inférieure en temps pour le problème 3-SATsvp ? Ou si rien n'a encore été démontré ?

    Merci !
    David
    2n
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  3. 15/05/2009, 14h52 #3
    invitedf72ed21

    Re : problème 3-SAT

    arg
    une vraie borne DEMONTREE !
  4. 15/05/2009, 16h47 #4
    invitedf72ed21

    Re : problème 3-SAT

    Toujours pas de réponse ?
  5. Aujourd'hui
    A voir en vidéo sur Futura
  6. 16/05/2009, 10h27 #5
    acx01b

    Re : problème 3-SAT

    tous les problèmes non déterministes polynomiaux (NP) se réduisent à 3-SAT
  7. 16/05/2009, 10h30 #6
    acx01b

    Re : problème 3-SAT

    ha oui et certains problèmes 3 SAT peuvent se résoudre facilement (en temps linéaire) par exemple si les variables apparaissent dans 1 seule clause

    donc c'est plutôt un problème 3 SAT particulier (de préférence un des plus difficiles) qu'il serait intéressant de minorer
« Analyse MPSI J. Monier | énumération des premiers »

Discussions similaires

  1. [Divers] probleme antenne sat
    Par invite22cd01ab dans le forum Dépannage
    Réponses: 2
    Dernier message: 04/08/2008, 14h43
  2. Problème branchement TV / SAT
    Par invite75470a6d dans le forum Dépannage
    Réponses: 5
    Dernier message: 14/01/2008, 16h57
  3. [Brun] Probleme De Reception Antenne Sat
    Par invitea6bba5fb dans le forum Dépannage
    Réponses: 4
    Dernier message: 15/06/2007, 17h56
  4. [Brun] probleme demo numerique sat star1700
    Par invite2d971ea8 dans le forum Dépannage
    Réponses: 0
    Dernier message: 26/12/2006, 18h38
  5. Probleme De Reinstallation De Pilote Toshiba Sat 1620cds
    Par invite52855976 dans le forum Matériel - Hardware
    Réponses: 1
    Dernier message: 15/08/2005, 22h04