Aqui está um problema com um sabor semelhante ao aprendizado de juntas:
Entrada: Uma função , representada por um oracle de associação, ou seja, um oracle que forneceu , retorna .
Objetivo: Encontre um subcubo de com volume modo que . Assumimos que esse subcubo exista.
É fácil obter um algoritmo que seja executado no tempo e retorne uma resposta correta com probabilidade , tentando todas as maneiras de escolher um subcubo e amostrar a média em cada um. ≥ 0,99 ( 2 n ) k
Eu sou interessante em encontrar um algoritmo que é executado no tempo . Como alternativa, um limite inferior seria ótimo. O problema tem um sabor semelhante ao aprendizado de juntas, mas não vejo uma conexão real entre as dificuldades computacionais.
Atualização: @Thomas abaixo prova que a complexidade da amostra deste problema é . A questão interessante é, ainda, a complexidade computacional do problema.
Edit: você pode assumir por simplicidade que existe um subcubo com (observe a lacuna: estamos procurando um subcubo com média .) Tenho certeza de que qualquer solução para o problema da lacuna também resolverá o problema sem a lacuna.≥0,1
fonte