{"entities":{"Q802309":{"pageid":804157,"ns":120,"title":"Item:Q802309","lastrevid":64486548,"modified":"2026-04-11T20:11:57Z","type":"item","id":"Q802309","labels":{"en":{"language":"en","value":"On small generators"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3890732"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$6B48E4E5-B5A0-4CC3-8354-DE14E9F7EA3D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b614014c97f05c77ed65fff39cc47715a5e485d6","datavalue":{"value":{"text":"On small generators","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q802309$45255D15-D200-4D4D-B529-782F91A440AE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4ce38eaebba2d6eb3fbb48cfed3dcbeb3fa5de6","datavalue":{"value":"0558.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802309$CE5AF8E5-FF38-4143-9716-8A4842C7C97F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5345f1fab4c4080b04282eb1dcab57b84065ec92","datavalue":{"value":"10.1016/0304-3975(84)90058-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802309$7177FE9B-36A0-48BE-A636-90A90DCD3670","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$42934924-D929-47DE-A5A4-0D1BAAA78950","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q802309$0287ED33-21C1-423A-B391-3F5AE750222B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7459b4b795605916f648db4ff7a08c604803b184","datavalue":{"value":"\\textit{C. K. Yap} [Theor. Comput. Sci. 26, 287-300 (1983; Zbl 0541.68017)] has shown that each set having small ''generating'' circuits is in the class NP/Poly which was introduced by \\textit{R. M. Karp} and \\textit{R. J. Lipton} [Proc. 12th Ann. ACM Symp. Theory of Computing, 302-309 (1980)]. In this paper it is shown that the converse is also true, i.e. each set in NP/Poly has small generators. This settles a question left open by Yap. Further, it is shown that, under certain conditions on C, a set A is in C/Poly if and only if \\(A\\in C(S)\\) for some sparse set S. Specifically, a set has small generators if and only if there is a sparse oracle S with \\(A\\in NP(S)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q802309$FD28383E-D006-4F64-9D3F-670DF25CC162","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802309$1D55832E-A03B-4848-9C12-C9AE6FE4B304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802309$FCE20417-EAF9-46BE-8DBF-309F9C9DAD83","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"beab6bdfb2d2e0a9282903c6400c70ccf8062236","datavalue":{"value":"3890732","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802309$F2F9E038-CE61-4992-AFAE-E22F28D4DF0B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q802309$150813BF-8FE0-46D0-8E6B-31445B39B634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ffd2c11d59e87e286f03c959c5f7bf253a86cee","datavalue":{"value":"NP/Poly","type":"string"},"datatype":"string"},"type":"statement","id":"Q802309$6F587372-5DC3-433A-9B94-5B3F046EAB70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b302eea3c175051b08ae21ed3ffc354cb887962","datavalue":{"value":"sparse oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q802309$AB5E4EF6-4F05-46DC-A925-62BD38BE0791","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98e020d336f4040f2344877fb27890751f480383","datavalue":{"value":{"entity-type":"item","numeric-id":1052096,"id":"Q1052096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$84A7FFB0-DF7F-4441-AC88-2446CC9200F2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$38A5F579-D379-43DD-8E49-9C87493DA248","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9af78bbd8b99f2d321eeac5d12d26e9b6e8bb406","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90058-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q802309$1F3B4D02-0637-4D70-AA4C-D329DF0E5553","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f40759a514baf6c4483573ac77cec1648eff32f8","datavalue":{"value":"W2004060519","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802309$299D0FBC-26D6-403F-A6AF-D71EE86AEF13","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$C888397F-5164-44B6-BE4D-3E5E8E67CF9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$F9C3E162-9E2D-4143-87B9-82A5138F695A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c62de5048fa954af00b82660416a315c8b87034","datavalue":{"value":{"entity-type":"item","numeric-id":1164997,"id":"Q1164997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$83BD56B9-AAF1-4586-B709-40672070BE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$4B6AD816-2FF1-4650-A532-78760BFDFC0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$289F08D2-7152-4DC7-8596-C4D71DD4217A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ef86d27229f88234625ab5cf631770a7bacc164","datavalue":{"value":{"entity-type":"item","numeric-id":794427,"id":"Q794427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802309$74A59E14-51D2-4763-9B08-4CCFFCA95FDE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17df17e20af88e7233c5de4c8e44e983c9fa7ca0","datavalue":{"value":{"entity-type":"item","numeric-id":4277541,"id":"Q4277541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d18c765fc94aa861fec12bad07ccf412744e589","datavalue":{"value":{"amount":"+0.7579531073570251","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q802309$83A26C85-16E7-46E7-9E21-7C07D1AC9D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d0c85e38fc5207562d8e03a770528015c400d21","datavalue":{"value":{"entity-type":"item","numeric-id":4258583,"id":"Q4258583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e3cbc4458a65b8b5db1e2fa4c2aa4023a918b31","datavalue":{"value":{"amount":"+0.7399084568023682","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q802309$F67C5800-286C-4BA5-9F32-29198AA6F878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88ecdedeaf6afee30efcad8beda21e59fde3ae23","datavalue":{"value":{"entity-type":"item","numeric-id":4645178,"id":"Q4645178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bf3ad2eb59e45b89304340b1d3bbe2b37f9a39d","datavalue":{"value":{"amount":"+0.7394778728485107","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q802309$2ECFE923-BA89-4774-8500-E6370E6B4D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d66fc7f7c444da990219f313bf104114db21038b","datavalue":{"value":{"entity-type":"item","numeric-id":3323851,"id":"Q3323851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aeeba9eb91f1d01d022be3fe58273d771fdd782a","datavalue":{"value":{"amount":"+0.7370736598968506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q802309$A9D51F40-66D2-4530-B000-8497930B08A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"509d28fe0f20420ef6a8e2775a4e66cb10825215","datavalue":{"value":{"entity-type":"item","numeric-id":3034825,"id":"Q3034825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f504649f4aabe5a578cd012010f4795d88ba5f27","datavalue":{"value":{"amount":"+0.7346440553665161","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q802309$181AB221-8C7E-4E65-8EEF-0700E98297FA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On small generators","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_small_generators"}}}}}