Permettez à une machine de Turing probabiliste d'avoir accès à une pièce de monnaie injuste qui génère des probabilités (les flips sont indépendants). Définissez comme la classe de langages reconnaissable par une telle machine en temps polynomial. Il s'agit d'un exercice standard pour prouver que:B...
Les estimateurs biaisés sont utiles en statistique car ils peuvent optimiser l'erreur quadratique moyenne plus que ce qu'un estimateur non biaisé peut gérer . Je me demandais si en théorie CS il y avait des exemples très remarquables de l'utilisation efficace d'estimateurs biaisés. Je me rends...
Y a-t-il eu des tentatives pour montrer que le caractère aléatoire de Kolmogorov serait suffisant pour RP ? La probabilité utilisée dans l'énoncé "Si la bonne réponse est OUI, alors elle (la machine probabiliste de Turing) renvoie OUI avec probabilité ..." serait-elle toujours bien définie dans ce...
Il semble y avoir de nombreux algorithmes randomisés pour les tests d'identité polynomiale, vérifiant si un polynôme donné est nul ou non. Y a-t-il des résultats d'algorithmes qui font une sorte d'estimation des polynômes sur un ensemble spécifique de points? Cela pourrait être, par exemple, une...
Que soit une classe de complexité et BP- C la contrepartie aléatoire de C définie comme BPP par rapport à P . Plus formellement, nous fournissons un nombre aléatoire de bits polynomial et nous acceptons une entrée si la probabilité d'accepter est supérieure à
Considérez le problème suivant. Il existe valeurs inconnues . La tâche consiste à rechercher l'index du plus grand en utilisant uniquement les requêtes du formulaire suivant. Une requête est spécifiée par un ensemble et la réponse correspondante est . L'objectif est d'utiliser le moins de requêtes...
Que soit une classe de complexité et BP- C la contrepartie aléatoire de C défini de la même manière que BPP est défini par rapport à P . Plus formellement, nous fournissons polynomialement de nombreux bits aléatoires et nous acceptons une entrée si la probabilité d'accepter est supérieure à...
Étant donné le coprime , pouvez-vous calculer rapidementa,ba,ba, bminx,y>0|ax−by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Ici x,yx,yx, y sont des entiers. Évidemment, prendre x=y=0x=y=0x = y = 0 donne une réponse sans intérêt; en général, à quel point ces pouvoirs peuvent-ils se...
Je sais que le temps d'exécution le plus défavorable attendu de l'algorithme de triangulation incrémentielle delaunay randomisé (tel que donné dans Computational Geometry ) est . Il y a un exercice qui implique que le pire temps d'exécution est Ω ( n 2 ) . J'ai essayé de construire un exemple où...