Presque toujours presque raison

11

Je suis à la recherche d'une classe de complexité qui se rapporte à APX comme BPP se rapporte à P. J'ai déjà posé la même question ici , mais peut-être TCS serait un endroit plus fructueux pour les réponses.

La raison de la question est que dans les problèmes pratiques, il faut souvent trouver des réponses approximatives (donc APX) avec une confiance suffisamment élevée (donc BPP), ce qui ferait de la classe de problèmes avec des algorithmes d'approximation probabiliste bornés potentiellement un modèle utile de ce qui est calculable dans entraine toi.

Un candidat possible d'une telle classe serait : problèmes qui admettent des solutions approchées avec des sous-programmes probabilistes bornés; cependant, je ne suis pas convaincu qu'une telle classe serait le réglage approprié pour les approximations de classe calculables de manière probabiliste.APXBPP

Le BPP et l'APX ont tous deux été largement étudiés. Est-ce le cas pour , ou quelle classe serait la meilleure pour saisir les problèmes ci-dessus?APXBPP

cc.complexity-theory approximation-hardness Michael
la source
BPP et P sont des classes de problèmes de décision. Peut-être que vous devriez d'abord demander quelle est la classe fonction / recherche correspondant à BPP avant de passer à l'approximation, je pense que si nous avons la classe fonction / recherche, la définition de sa version d'approximation ne devrait pas être difficile.
Kaveh
1
Je pense que ce que vous recherchez est la version d'optimisation de l'apprentissage PAC (probablement approximativement correct). Alors que la théorie de l'apprentissage PAC concerne spécifiquement (au hasard, avec probablement une grande exactitude) les fonctions d' apprentissage pour décrire les données, comme dans l'apprentissage automatique, vous vous interrogez sur les problèmes d'optimisation. Pourtant, peut-être que la littérature d'apprentissage PAC est un bon endroit pour commencer la recherche ...
Joshua Grochow
3
Plutôt que la notation Oracle, ce que vous décrivez est plus proche de l'opérateur BP. L'opérateur BP est défini sur les classes de complexité des problèmes de décision. Il devrait être facile d'étendre la définition pour promettre des problèmes et de définir ainsi une version de problème de promesse de votre classe de complexité. La définition d'une version pour les problèmes d'optimisation peut être plus délicate.
Sasho Nikolov

Réponses:

1

Pour une fonction objective donnée, laissez BotL (le meilleur de la liste) être l'algorithme qui évalue la fonction objectif sur un ensemble d'entrées et renvoie une entrée de cette liste qui avait une sortie maximale (parmi ces entrées), avec des liens cassé arbitrairement. Comme APX n'inclut que les problèmes
dont la fonction objective peut être calculée en temps polynomial déterministe, BotL peut être implémenté de manière déterministe en temps polynomial.En outre, la valeur renvoyée par BotL
est au moins aussi bonne que n'importe quelle entrée dans le moins sur laquelle BotL a été évalué.En particulier,
si l'une des entrées de cette liste est suffisante, la sortie de BotL sera suffisante.
Par conséquent, l'exécution de BotL sur les sorties d'un nombre suffisamment important d'exécutions indépendantes d'un algorithme de base peut amplifier la probabilité de réussite de 1 / poly à 1- (1 / (2 ^ poly)).

En conséquence du paragraphe précédent, le
niveau de confiance précis n'affecte essentiellement pas la classe résultante.
(Cette situation est très analogue à RP .)

Je n'ai rien trouvé à ce sujet sur le zoo de la complexité, bien qu'il y ait
peut-être eu des discussions à ce sujet lors de l'atelier mentionné dans cet article .


la source
1
OP demande le nom de la classe de problèmes qui ont des algorithmes d'approximation à facteur constant randomisés. Vous dites (je pense) que la probabilité de succès de tels algorithmes peut être amplifiée. Je ne vois pas comment cela répond à la question?
Sasho Nikolov
Je ne vois pas cette question dans le PO. Michael demande si la classe a "fait l'objet d'une étude approfondie". Certes, je n'avais pas grand-chose à dire à ce sujet, mais j'ai (au moins essayé) de résoudre un malentendu sur ce que serait une telle classe.
Il n'y a pas un tel malentendu dans la question.
Sasho Nikolov
Droite. Le malentendu est dans le "Un candidat possible d'une telle classe serait ... approximations calculables de manière probabiliste." paragraphe, qui est dans le message, mais pas la question.
1
Avec les clarifications, je suis toujours d'avis que votre réponse ne corrige pas un malentendu dans le PO, mais donne simplement un fait arbitraire sur les approximations aléatoires.
Sasho Nikolov