bonjour alors voila je sais pas quoi repondre aux deux dernieres questions, ni l'inclusion 1, 2 et 4...
pouvez vous m'aider svp ?
Pour les inclusions :
1. NP inclus dans NPSPACE puisque chaque étape de calcul écrit au plus une case mémoire, ça marche avec ou sans oracles on s'en fiche
2. QSAT est dans PSPACE, tu peux remplacer chaque appel à l'oracle par le vrai algo QSAT, et au total t'es encore dans NPSPACE.
4. Utilise le fait que QSAT est PSPACE-complet
Pour la (4), t'as juste à suivre l'indication. Regarde ce que fait M_i0 sur l'entrée 1^i0, et compare à la définition de B_i0.
- Si M_i0 accepte 1^i0 alors [...] (contradiction)
- et si M_i0 rejette 1^i0 alors [...] (contradiction aussi)
Pour la (5) je vois pas
merci mon bro
En fait pour la question (5) il faut juste remarquer qu'à la question 3 on avait en fait card(U Xj) < 2^(i-1). Du coup, soit Bi est vide, soit Bi contient au moins la moitié des mots de {0,1}^i.
Du coup à chaque fois que tu testes un mot de {0,1}^i au hasard, si Bi est non-vide, t'as une proba >1/2 de tomber sur un mot de Bi. Tu répètes ça 10 fois et t'auras une proba <1/1000 de te planter.
Le 13 avril 2019 à 23:56:14 Niverolle a écrit :
Pour les inclusions :
1. NP inclus dans NPSPACE puisque chaque étape de calcul écrit au plus une case mémoire, ça marche avec ou sans oracles on s'en fiche
2. QSAT est dans PSPACE, tu peux remplacer chaque appel à l'oracle par le vrai algo QSAT, et au total t'es encore dans NPSPACE.
4. Utilise le fait que QSAT est PSPACE-completPour la (4), t'as juste à suivre l'indication. Regarde ce que fait M_i0 sur l'entrée 1^i0, et compare à la définition de B_i0.
- Si M_i0 accepte 1^i0 alors [...] (contradiction)
- et si M_i0 rejette 1^i0 alors [...] (contradiction aussi)Pour la (5) je vois pas
du coup j'ai :
Si M_io accepte 1^i0 alors il existe un m tel que 1^|m| appartient à B_io(barre) et m appartient à B_io or B_io est vide donc contradiction
et elle est en complexité < 2^n/4 car si M_io accepte alors elle accepte avant le timeout
Le 15 avril 2019 à 16:23:53 Fuligule a écrit :
En fait pour la question (5) il faut juste remarquer qu'à la question 3 on avait en fait card(U Xj) < 2^(i-1). Du coup, soit Bi est vide, soit Bi contient au moins la moitié des mots de {0,1}^i.
Du coup à chaque fois que tu testes un mot de {0,1}^i au hasard, si Bi est non-vide, t'as une proba >1/2 de tomber sur un mot de Bi. Tu répètes ça 10 fois et t'auras une proba <1/1000 de te planter.
je vois pas d ou tu tiens 2^(i-1)
et elle est en complexité < 2^n/4 car si M_io accepte alors elle accepte avant le timeout
c'est le contraire, dans la question 4 tu supposes que M_i0 accepte en complexité 2^m/4, c'est ça qui te permet de dire que soit elle accepte, soit elle rejette (elle ne peut pas timeout)
je vois pas d ou tu tiens 2^(i-1)
Somme de 0 à i de 2^j/4 = 2^(i+1)/4 = 2^(i-1)
c'est le contraire, dans la question 4 tu supposes que M_i0 accepte en complexité 2^m/4, c'est ça qui te permet de dire que soit elle accepte, soit elle rejette (elle ne peut pas timeout)
oui dans l autre sens, le reste est correct?
Somme de 0 à i de 2^j/4 = 2^(i+1)/4 = 2^(i-1)
bien vu ca venait de la 1ere affirmation. je pensais que t'as fait un typo sur la 2e.
Oui c'est OK pour la contradiction. Il faut faire pareil pour M_i0 rejette 1^i0
jy suis pas arrivé mais ya vraiment besoin? si on fait pour 1 cas ca suffit pour dire qu'elle ne calcule pas la bonne chose
Ben non ça suffit pas, pour l'instant tu as juste montré qu'elle ne pouvait pas accepter le mot 1^i0 mais rien ne te dit que ce mot devrait être accepté.
Il te reste soit a prouver 1^i0 doit être accepté (càd, que B_i0 est non vide), soit à supposer que la machine refuse 1^i0 et aboutir à une contradiction. Dans les deux cas l'argument sera le même (en particulier il faut utiliser la question 3)
ok je vais essayer ce soir
juste par curiosité tu as déja vu ce sujet ?
Non mais c'est un argument diagonal classique
ok
donc dans l autre sens :
Si M io ne reconnait pas 1 io, ca veut dire qu'il nexiste pas de mot m de longueur io tel que m appartient à Bio or Bio n'est pas vide
et la on a deux contradiction et cest bon?
Oui
super merci fuligule
si ca tinteresse je peux scanner le reste de l'examen, cest des reductions depuis sat vers des problemes