Quase sempre quase certo

Estou procurando uma classe de complexidade que se relacione ao APX e o BPP ao P. Já fiz a mesma pergunta aqui , mas talvez o TCS seja um local mais proveitoso para respostas.

A razão para a pergunta é que, em problemas práticos, geralmente é necessário encontrar respostas aproximadas (portanto APX) com confiança suficientemente alta (assim BPP), o que tornaria a classe de problemas com algoritmos de aproximação probabilística limitada potencialmente um modelo útil do que é computável em prática.

Um possível candidato dessa classe seria : problemas que admitem soluções aproximadas com sub-rotinas probabilísticas limitadas; no entanto, não tenho certeza de que essa classe seja a configuração apropriada para as aproximações probabilisticamente computáveis da classe. $APX^{BPP}$

O BPP e o APX foram extensivamente estudados. É esse o caso do ou de qual classe seria a melhor para capturar os problemas acima? $APX^{BPP}$

cc.complexity-theory approximation-hardness Michael
fonte

BPP e P são classes de problemas de decisão. Talvez você deva primeiro perguntar qual é a classe de função / pesquisa correspondente ao BPP antes de passar para a aproximação. Acho que, se tivermos a classe de função / pesquisa, a definição de sua versão de aproximação não deve ser difícil.

Kaveh

Acho que o que você está procurando é a versão de otimização do aprendizado do PAC (provavelmente aproximadamente correto). Enquanto a teoria do aprendizado do PAC é especificamente sobre (aleatoriamente, com alta probabilidade de correção) as funções de aprendizado para descrever dados, como no aprendizado de máquina, você está perguntando sobre problemas de otimização. Ainda assim, talvez a literatura aprender PAC é um bom lugar para começar a procurar ...

Joshua Grochow

Em vez da notação oracle, o que você está descrevendo está mais próximo do operador BP. O operador BP é definido em classes de complexidade de problemas de decisão. Deve ser fácil estender a definição para prometer problemas e definir dessa maneira uma versão do problema de promessa da sua classe de complexidade. Definir uma versão para problemas de otimização pode ser mais complicado.

Sasho Nikolov

Respostas:

Para qualquer função objetivo, seja BotL (o melhor da lista) o algoritmo que avalia a função objetivo em um conjunto de entradas e retorna uma entrada dessa lista que teve saída máxima (dentre essas entradas), com vínculos quebrado arbitrariamente. Como o APX inclui apenas problemas cuja função objetivo pode ser calculada em tempo polinomial determinístico, o BotL pode ser implementado deterministicamente em tempo polinomial. Além disso, o valor retornado pelo BotL é pelo menos tão bom quanto qualquer uma das entradas no mínimo em que o BotL foi avaliado. Em particular, se alguma das entradas nessa lista for boa o suficiente, a saída do BotL será boa o suficiente. $\:$
$\:$
$\:$

Portanto, executar BotL nas saídas de um número suficientemente grande de execuções independentes de um algoritmo de base pode amplificar a probabilidade de sucesso de 1 / poli a 1- (1 / (2 ^ poli)).

Como conseqüência do parágrafo anterior, o
nível preciso de confiança não afeta essencialmente a classe resultante.
(Essa situação é altamente análoga à RP .)

Não pude encontrar nada sobre isso no zoológico de complexidade, embora
possa ter havido conversas sobre o assunto no workshop mencionado neste artigo .

fonte

O OP está solicitando o nome da classe de problemas que possuem algoritmos aleatórios de aproximação de fator constante. Você está dizendo (eu acho) que a probabilidade de sucesso de tais algoritmos pode ser ampliada. Não estou conseguindo ver como isso responde à pergunta?

Sasho Nikolov

Não vejo essa pergunta no OP. Michael está perguntando se a classe "foi extensivamente estudada". É verdade que não tenho muito a dizer sobre isso, mas (pelo menos tentei) abordar um mal-entendido sobre o que seria essa classe.

$\:$

$\;\;\;$

Não existe tal mal-entendido na questão.

Sasho Nikolov

Certo. O mal-entendido está no "Um possível candidato dessa classe seria ... aproximações probabilisticamente computáveis". parágrafo, que está no post, mas não a pergunta.

$\:$

$\;\;\;$

Com os esclarecimentos, ainda é minha opinião que sua resposta não está corrigindo um mal-entendido no PO, mas apenas fornece um fato arbitrário sobre aproximações aleatórias.

Sasho Nikolov