|
[x]
Posted via EE Mobile
|
|
| Search, ask, and monitor your questions on the go with EE Mobile. Visit Experts Exchange from your mobile device and never be out of touch again. |
|
|
|
|
Asked by Karks in Theory, Algorithms, Math & Science
Let H be the class of all Turing machines (not necessarily polynomial time)
thus, the output of the learning algorithm can be any program.
Show that if Cn is the class of all boolean circuits of size at most p(n)
for some fixed polynomial, then C is efficiently PAC learnable using H.
Argue that your solution shows that this relaxation trivializes the model of
learning.
Any ideas?
20091111-EE-VQP-89 - Hierarchy / EE_QW_3_20080625
