We consider the problem of determining the VC-dimension d(3)(h) of depth four n-input 1-output threshold circuits with h elements. Best known asymptotic lower bounds and upper bounds are proved, that is, when h --> infinity, d(3)(h) is upper bounded by ((h(2)/3)+nh)(logh)(1+o(1)) and lower bounded by (1/2)((h(2)/4) +nh)(logh)(1-o(1)). We also consider the problem of determining the complexity C-3(N)(c(3))(N)) of Boolean functions defined on N-pointsets of vertices of n-dimensional hypercube (Boolean-valued functions defined on N-pointsets in R(n), respectively), measured by the number of threshold elements, with which we can construct a depth four circuit to realize the functions. We also show the best known upper and lower bounds, that is, when N-->infinity, C-3(N) upper bounded by root 32(N/logN)(1+o(1)) and lower bounded by root 6(n/logN)(1-o(1)) and c(3)(N) is upper bounded by root 16(N/logN)(1+o(1))+4n(2)-2n and lower bounded by root 6(N/logN)(1-o(1))+(9/4)n(2)-(3/2)H. [References: 12]
展开▼
