{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:22:29Z","timestamp":1775053349978,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1991,5,1]],"date-time":"1991-05-01T00:00:00Z","timestamp":673056000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1991,5,1]],"date-time":"1991-05-01T00:00:00Z","timestamp":673056000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Learning"],"published-print":{"date-parts":[[1991,5]]},"DOI":"10.1023\/a:1022657626762","type":"journal-article","created":{"date-parts":[[2003,4,4]],"date-time":"2003-04-04T16:55:36Z","timestamp":1049475336000},"page":"211-230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Complexity Results on Learning by Neural Nets"],"prefix":"10.1007","volume":"6","author":[{"given":"Jyh-Han","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"423123_CR1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1162\/neco.1989.1.1.151","volume":"1","author":"E. Baum","year":"1989","unstructured":"Baum, E., & Haussler, D.(1989). What size net gives valid generalization? Neural Computation, 1,151\u2013160.","journal-title":"Neural Computation"},{"key":"423123_CR2","unstructured":"Blum, A., & Rivest, R. L.(1988). Training a 3-node neural network is 316 \u211c\u2118-complete. Proceedings of the First ACM Workshop on the Computational Learning Theory (pp.9\u201318). Cambridge, MA."},{"key":"423123_CR3","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K.(1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36, 929\u2013965.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"423123_CR4","volume-title":"Threshold logic:A synthesis approach","author":"M. L. Dertouzos","year":"1965","unstructured":"Dertouzos, M. L.(1965).Threshold logic:A synthesis approach. Cambridge, MA: MIT Press."},{"key":"423123_CR5","volume-title":"Computers and intractability:A guide to the theory of3l9-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S.(1979).Computers and intractability:A guide to the theory of3l9-completeness. San Francisco, CA: W. H. Freeman and Co."},{"key":"423123_CR6","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0004-3702(88)90002-1","volume":"36","author":"D. Haussler","year":"1988","unstructured":"Haussler, D.(1988). Quantifying inductive bias:AI learning algorithms and Valiant's learning framework. Artificial Intelligence, 36, 177\u2013221.","journal-title":"Artificial Intelligence"},{"key":"423123_CR7","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0004-3702(89)90049-0","volume":"40","author":"G. E. Hinton","year":"1989","unstructured":"Hinton, G. E.(1989). Connectionist learning procedures.Artificial Intelligence, 40, 185\u2013234.","journal-title":"Artificial Intelligence"},{"key":"423123_CR8","unstructured":"Judd, J. S.(1987). Complexity of connectionist learning with various node functions.(COINS Technical Report No.87\u201360). University of Massachusetts."},{"key":"423123_CR9","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0885-064X(88)90019-2","volume":"4","author":"J. S. Judd","year":"1988","unstructured":"Judd, J. S.(1988). On the complexity of loading shallow neural networks. Journal of Complexity, 4, 177\u2013192.","journal-title":"Journal of Complexity"},{"key":"423123_CR10","unstructured":"Masek, W. J.(1978). Some SiKP-complete set cover problems. MIT Laboratory for Computer Science, unpublished manuscript."},{"key":"423123_CR11","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5236.001.0001","volume-title":"Parallel distributed processing","author":"D. E. Rumelhart","year":"1986","unstructured":"Rumelhart, D. E., Hinton, G. E., & Williams, R. J.(1986). Learning internal representations by error propagation. In D. E. Rumelhart & I. E. McClelland (Eds.),Parallel distributed processing. Cambridge, MA: MIT Press."},{"key":"423123_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L. J.(1977). The polynomial-time hierarchy. Theoretical Computer Science, 3, 1\u201322.","journal-title":"Theoretical Computer Science"},{"key":"423123_CR13","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L. J., & Meyer, A. R.(1973). Word problems requiring exponential time:Preliminary report. Proceed-ings of the fifth Annual Symposium on the Theory of Computing (pp.1\u20139).","DOI":"10.1145\/800125.804029"},{"key":"423123_CR14","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G.(1984). A theory of the learnable.Communications of the ACM, 27, 1134\u20131142.","journal-title":"Communications of the ACM"},{"key":"423123_CR15","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1162\/neco.1989.1.1.39","volume":"1","author":"A. Weibel","year":"1989","unstructured":"Weibel, A.(1989). Modular construction of time-delay neural networks for speech recognition. Neural Computa tion, 1, 39\u201346.","journal-title":"Neural Computa tion"},{"key":"423123_CR16","unstructured":"Weibel, A., & Hampshire, J.(1989). Building blocks for speech. Byte, August, 235\u2013242."},{"key":"423123_CR17","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"Wrathall, C.(1977). Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3, 23\u201333.","journal-title":"Theoretical Computer Science"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1022657626762.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1022657626762\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1022657626762.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T11:34:27Z","timestamp":1752147267000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1022657626762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,5]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,5]]}},"alternative-id":["423123"],"URL":"https:\/\/doi.org\/10.1023\/a:1022657626762","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,5]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}