Kompleksitas kueri komputasi dari pembelajaran SQ

Diketahui bahwa untuk pembelajaran PAC, ada kelas konsep alami (misalnya himpunan bagian dari daftar keputusan) yang terdapat kesenjangan polinomial antara kompleksitas sampel yang diperlukan untuk pembelajaran teori informasi oleh pelajar yang tidak terikat secara komputasi, dan kompleksitas sampel yang dibutuhkan oleh polinomial- pelajar waktu. (lihat, mis. http://portal.acm.org/citation.cfm?id=267489&dl=GUIDE atau http://portal.acm.org/citation.cfm?id=301437 )

Namun, hasil ini tampaknya bergantung pada penyandian rahasia dalam contoh-contoh tertentu, dan karenanya tidak secara alami diterjemahkan ke dalam model pembelajaran SQ, di mana pelajar hanya perlu menanyakan properti statistik distribusi.

Apakah diketahui apakah ada kelas konsep yang pembelajaran informasi-teoretisnya dalam model SQ dimungkinkan dengan kueri O (f (n)), tetapi pembelajaran yang efisien secara komputasi hanya dimungkinkan dengan kueri Omega (g (n)) untuk g (n) ) >> f (n)?

Saya telah menanyakan (sendiri) pertanyaan ini beberapa waktu yang lalu. Setidaknya untuk pembelajaran berkenaan dengan distribusi tertentu ada contoh yang cukup sederhana dari kelas konsep yang informasi secara teoritis SQ-dapat dipelajari tetapi NP-sulit untuk SQ belajar. Biarkan \ phi pengodean biner dari instance SAT dan y menjadi penugasan pertama yang memuaskan secara leksikografis (atau 0 ^ n adalah instance tidak memuaskan). Sekarang mari f (\ phi) menjadi fungsi yang lebih dari setengah dari domain adalah MAJ (\ phi) dan lebih dari setengah kedua domain sama dengan PAR (y). Di sini MAJ adalah fungsi mayoritas atas variabel yang ditetapkan ke 1 dalam string \ phi dan PAR (y) adalah fungsi paritas atas variabel yang ditetapkan ke 1 dalam string y. Biarkan F menjadi kelas fungsi yang diperoleh dengan cara ini. Untuk SQ belajar F melalui distribusi seragam, Anda hanya perlu mempelajari mayoritas (yang mudah) untuk menemukan \ phi dan kemudian menemukan y. Di sisi lain, cukup mudah untuk mengurangi pembelajaran SAT ke SQ dari F (ke akurasi yang terlihat lebih besar dari 3/4) pada distribusi yang seragam. Alasan untuk ini, secara alami, adalah bahwa paritas pada dasarnya "tidak terlihat" untuk SQ dan oleh karena itu perlu untuk menyelesaikan SAT untuk belajar F.

Ini pertanyaan yang bagus. Kekuatan model kueri statistik adalah kemampuan untuk membuktikan batas bawah tanpa syarat untuk belajar dengan SQ - misalnya, paritas tidak dapat dipelajari dengan kueri statistik jumlah polinomial.

Saya tidak mengetahui hasil dari formulir yang Anda minta, tapi mungkin kita kehilangan sesuatu yang jelas ...