{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T05:30:02Z","timestamp":1697520602941},"reference-count":10,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2002,1,4]],"date-time":"2002-01-04T00:00:00Z","timestamp":1010102400000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[2002,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Learning from examples in the presence of overwhelmingly many irrelevant variables has been studied in the field of machine learning theory, where the learner is required to derive as succinct hypotheses as possible. In this paper, we consider the following computational learning problem: Given a set of negative examples in <jats:italic>n<\/jats:italic> Boolean variables, the learner is required to find <jats:italic>O<\/jats:italic>(log <jats:italic>n<\/jats:italic>) relevant variables whose conjunction gives a consistent hypothesis. This problem belongs to a complexity class called \u03b2<jats:sub>2<\/jats:sub>. We prove that this problem is equivalent, by probabilistic log\u2010space Turing reduction, to the problem of finding satisfiable assignments for polynomial\u2010size <jats:styled-content>${\\bf \\Pi}^{0}_{3}$<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-ueqn-1.gif\" xlink:title=\"equation image\" \/><\/jats:styled-content>\u2010circuits with <jats:italic>O<\/jats:italic>(log<jats:sup>2<\/jats:sup> <jats:italic>n<\/jats:italic>) inputs. As a consequence, we can show that learning of <jats:italic>O<\/jats:italic>(log <jats:italic>n<\/jats:italic>)\u2010length Boolean conjunctions from negative examples is neither \u03b2<jats:sub>2<\/jats:sub>\u2010hard unless <jats:bold>P<\/jats:bold> \u2286 <jats:bold>POLYLOG\u2010SPACE<\/jats:bold>, nor polynomial\u2010time computable unless <jats:bold>NP<\/jats:bold> \u2286 <jats:bold>DTIME<\/jats:bold>(2<jats:sup><jats:italic>O<\/jats:italic>(\u221a<jats:italic>n<\/jats:italic>)<\/jats:sup>).<\/jats:p><jats:p>In this paper, we also discuss the polynomial\u2010time learnability of an <jats:italic>O<\/jats:italic>(log <jats:italic>n<\/jats:italic>)\u2010length monotone Boolean conjunction from negative examples, when the examples are drawn from the uniform distribution. \u00a9 2001 Scripta Technica, Syst Comp Jpn, 33(1): 1\u20137, 2002<\/jats:p>","DOI":"10.1002\/scj.1094","type":"journal-article","created":{"date-parts":[[2004,10,28]],"date-time":"2004-10-28T09:30:29Z","timestamp":1098955829000},"page":"1-7","source":"Crossref","is-referenced-by-count":0,"title":["Learning of Short Boolean Conjunctions from Negative Examples"],"prefix":"10.1002","volume":"33","author":[{"given":"Tatsuie","family":"Tsukiji","sequence":"first","affiliation":[]},{"given":"Takashi","family":"Tokutani","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2002,1,4]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90002-1"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365704"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090764"},{"key":"e_1_2_1_5_2","first-page":"123","article-title":"The Boolean formula value problem is in ALOGTIME","author":"Buss S.","year":"1987","journal-title":"Proc 19th STOC"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209003"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62685-9_15"},{"key":"e_1_2_1_8_2","volume-title":"Stochastic processes","author":"Ross SM.","year":"1996"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90057-8"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","first-page":"68","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An introduction to computational learning theory","author":"Kearns J","year":"1994"},{"key":"e_1_2_1_11_2","first-page":"87","volume-title":"Discovery science and dator mining (bit)","author":"Morishita S","year":"2000"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.1094","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.1094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T23:22:12Z","timestamp":1697498532000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.1094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["10.1002\/scj.1094"],"URL":"https:\/\/doi.org\/10.1002\/scj.1094","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}