Sabe-se que, para a aprendizagem do PAC, existem classes de conceitos naturais (por exemplo, subconjuntos de listas de decisão) para as quais existem lacunas polinomiais entre a complexidade da amostra necessária para o aprendizado da teoria da informação por um aprendiz computacionalmente ilimitado e a complexidade da amostra necessária para um aluno polinomial. aprendiz de tempo. (consulte, por exemplo, http://portal.acm.org/citation.cfm?id=267489&dl=GUIDE ou http://portal.acm.org/citation.cfm?id=301437 )
Entretanto, esses resultados dependem da codificação de um segredo em exemplos específicos e, portanto, não se traduzem naturalmente no modelo SQ da aprendizagem, onde o aluno apenas consulta as propriedades estatísticas da distribuição.
Sabe-se se existem classes de conceitos para as quais o aprendizado teórico da informação no modelo SQ é possível com consultas O (f (n)), mas o aprendizado computacionalmente eficiente só é possível com consultas Omega (g (n)) para g (n ) >> f (n)?
fonte