Savoir & Culture

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-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

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