{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T14:11:35Z","timestamp":1775484695180,"version":"3.50.1"},"reference-count":16,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1975,12,1]],"date-time":"1975-12-01T00:00:00Z","timestamp":186624000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":13743,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1975,12]]},"DOI":"10.1016\/0304-3975(75)90018-3","type":"journal-article","created":{"date-parts":[[2002,10,10]],"date-time":"2002-10-10T23:41:28Z","timestamp":1034293288000},"page":"161-183","source":"Crossref","is-referenced-by-count":16,"title":["A class of boolean functions with linear combinational complexity"],"prefix":"10.1016","volume":"1","author":[{"given":"L.H.","family":"Harper","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W.N.","family":"Hsieh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.E.","family":"Savage","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(75)90018-3_BIBEH72","series-title":"Report No. CU-CS-OD8-72","first-page":"14","article-title":"Practical decidability","author":"Ehrenfeucht","year":"1972"},{"key":"10.1016\/0304-3975(75)90018-3_BIBHA73","author":"Harper","year":"1973","journal-title":"Complexity made simple"},{"issue":"3","key":"10.1016\/0304-3975(75)90018-3_BIBHS72","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0001-8708(72)90021-7","article-title":"The Complexity of the marriage problem","volume":"9","author":"Harper","year":"1972","journal-title":"Advances in Math."},{"key":"10.1016\/0304-3975(75)90018-3_BIBHS74A","series-title":"Ph. C. Thesis","first-page":"51","article-title":"Intersection theorems for systems of finite vector spaces and other combinatorial results","author":"Hsieh","year":"1974"},{"key":"10.1016\/0304-3975(75)90018-3_BIBHS74B","article-title":"An Upper Bound for the Complexity of P3,5 Functions","author":"Hsieh","year":"1974","journal-title":"M.I.T. Project MAC Technical Report"},{"key":"10.1016\/0304-3975(75)90018-3_BIBLA70","series-title":"Optimization Theory for Large Systems","first-page":"46","author":"Lasdon","year":"1970"},{"issue":"1","key":"10.1016\/0304-3975(75)90018-3_BIBLU58","first-page":"23","article-title":"On the synthesis of contact networks","volume":"119","author":"Lupanov","year":"1958","journal-title":"Dokl. Akad. Nauk."},{"key":"10.1016\/0304-3975(75)90018-3_BIBME74","series-title":"Lecture notes for course 6.853","author":"Meyer","year":"1974"},{"key":"10.1016\/0304-3975(75)90018-3_BIBME74B","unstructured":"A. R. Meyer, Private communication (1974)"},{"issue":"4","key":"10.1016\/0304-3975(75)90018-3_BIBNE66","first-page":"999","article-title":"A Boolean function","volume":"7","author":"Ne\u010diporuk","year":"1966","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/0304-3975(75)90018-3_BIBRA74","author":"Rabin","year":"1974","journal-title":"Private communication"},{"issue":"4","key":"10.1016\/0304-3975(75)90018-3_BIBSA72","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1145\/321724.321731","article-title":"Computational work and time on finite machines","volume":"19","author":"Savage","year":"1972","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(75)90018-3_BIBSA74","article-title":"Combinational complexity of functions","author":"Savage","year":"1974","journal-title":"The Complexity of Computing"},{"key":"10.1016\/0304-3975(75)90018-3_BIBSC74","author":"Schnorr","year":"1974","journal-title":"Zwei lineare untere Schranken fur die Komplexit\u00e4t Boolescher Funktionen"},{"issue":"1","key":"10.1016\/0304-3975(75)90018-3_BIBSH49","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","article-title":"The Synthesis of two-terminal switching circuits","volume":"28","author":"Shannon","year":"1949","journal-title":"Bell Systems Tech. J."},{"key":"10.1016\/0304-3975(75)90018-3_BIBST74","article-title":"The Complexity of decision problems in automata theory and logic","author":"Stockmeyer","year":"1974","journal-title":"M.I.T. Project MAC Technical Report 133"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397575900183?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397575900183?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T11:53:26Z","timestamp":1554983606000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0304397575900183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975,12]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1975,12]]}},"alternative-id":["0304397575900183"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(75)90018-3","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1975,12]]}}}