{"entities":{"Q1095663":{"pageid":1106415,"ns":120,"title":"Item:Q1095663","lastrevid":69826941,"modified":"2026-04-13T10:36:48Z","type":"item","id":"Q1095663","labels":{"en":{"language":"en","value":"On solving hard problems by polynomial-size circuits"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4028902"}},"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":"Q1095663$DDF31FBE-65B8-4641-85A7-F9FF8A65011D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f4b26871e8e9e424730a8ba78a02cf38ce6201a7","datavalue":{"value":{"text":"On solving hard problems by polynomial-size circuits","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095663$52BB27AC-A5DD-4B09-B2A9-8DA2C99CE87D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c5933e07ba36cf066d38878d864ee33e3d52aed6","datavalue":{"value":"0632.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095663$BEE2DB8C-886C-45CB-AB92-714FA44D8B68","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"19b468924d7c38b539e1a197beb74862f486de0b","datavalue":{"value":"10.1016/0020-0190(87)90181-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095663$CF94EF28-6899-4BEE-B705-8522356F2772","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f11d29d2cbdb03c4d5ff90d92cbc2f1d658ba97d","datavalue":{"value":{"entity-type":"item","numeric-id":391197,"id":"Q391197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$D5CBA30D-9FB1-4FFD-88CA-BA5D52299F0B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$AD85A3BD-FABA-439E-94FB-45A0D3CC7828","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1095663$486D000C-4EA3-4520-9CE9-61229B7CFC88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c259c76d26d2ed6c2dd5ebd1e25c10a05265f547","datavalue":{"value":"This paper introduces the notions of immunity, complexity core, and Church-randomness for the nonuniform complexity class of languages accepted by polynomial-size circuit families, usually denoted as P/Poly. While it is not known whether \\(DTIME(2^{poly})\\) is contained in P/Poly, we show that there exist languages in EXSPACE that have the property of being immune, or having dense complexity core, or being Church-random with respect to the class P/Poly. Proofs of these results are based on techniques in generalized Kolmogorov complexity theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$9B64DAC9-240F-4393-99BE-368AE04A4D3C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095663$F96D6FE2-3CD4-42D3-BBFF-364FB206B0B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095663$B4C50547-12DD-4B82-8365-C740A1E6C8F5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"89b289f169386153a4d8aa58419ecb632a432d3c","datavalue":{"value":"4028902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095663$B297C455-D1E3-42D1-B873-73A3BD9FE520","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe708dcce91d571d1ebd3853007f0b16521f4c8a","datavalue":{"value":"Boolean circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$E4C82CAB-ED30-4A2C-A167-75661A162ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4881dceebcfc2cfaaf48b0eeca275f318bc3a7ae","datavalue":{"value":"hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$F8C7A1F7-AA7A-475D-BF46-3B7A124D819C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03ffb1534e6cb0fd5ac9e35b1504b18f751db04f","datavalue":{"value":"immunity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$4DD02679-9B42-4C8A-AF34-F36788B2DBAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"425c2475342181113b155cfef65add5e162cd1e8","datavalue":{"value":"complexity core","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$ED713C99-1231-4755-B4F2-BB62264CF439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89e7b27277ab78125b50af9a90bdcdb0dd4142ea","datavalue":{"value":"Church-randomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$FCE53EE4-F159-438A-9945-3ED7A1084DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8db1726c03c7059c08d69b8aca64a6baa1151a9","datavalue":{"value":"complexity class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$79F8193E-6DD3-4E6B-98CE-E2EE783BEBB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca05d73258b267c503510712471424f239222382","datavalue":{"value":"languages accepted by polynomial-size circuit families","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$7933F6BC-8855-4BD0-BCC6-CE2F100FEFE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095663$C37EDE2B-23C5-4FCB-ADB4-3DD1F79D5906","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":"Q1095663$3524D14A-FEFB-43A6-BDCA-E6FB4B7FAF1E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6ec8af035d9e8f4e157721d629dad743bbcc33d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90181-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095663$95A70DE6-ACA1-4EE0-8F85-ACE616CDC147","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"14e2af7e6d47a971d9b520642bf8d8457d0d3d44","datavalue":{"value":"W1977590950","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095663$CAA1A97A-77F4-41CD-B2C6-5E8F0BDF2274","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$55D5E8F2-0288-46B9-BBF3-5DC2C0CB1751","rank":"normal"},{"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":"Q1095663$9DA0BDB4-D280-4006-8618-7E53C34BE1A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a581f96e8cabd60b98280dbc93b840cb31eb7421","datavalue":{"value":{"entity-type":"item","numeric-id":3339289,"id":"Q3339289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$58F248E7-B372-468D-BA13-364B3F10CBF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"663c83b1b2405da7d703f0e171d190fef0cde5dd","datavalue":{"value":{"entity-type":"item","numeric-id":5541327,"id":"Q5541327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$26434824-B6A6-433B-A14D-5B949F2A1F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec2b4a5af183cf7ee7783a80345d09671a84367a","datavalue":{"value":{"entity-type":"item","numeric-id":3769964,"id":"Q3769964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$5EB13E8A-3198-4606-A7F1-52EF661DE96D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bb9ae7a4d51bcc66e61116a729c20b41cd64f20","datavalue":{"value":{"entity-type":"item","numeric-id":3756525,"id":"Q3756525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$5E2F0035-7804-403E-8AAB-E2AD1AD0FFDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad60a730d7197c0e07353c23ef73b9d2e3d4a2dd","datavalue":{"value":{"entity-type":"item","numeric-id":3751001,"id":"Q3751001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$A41181C3-110C-4971-8A8B-56F714226D99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d83904af4ce7c3045229ccaec38d75eff59e768c","datavalue":{"value":{"entity-type":"item","numeric-id":3323851,"id":"Q3323851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$80AC13CC-7034-4F95-B2B5-BC7F46AF279C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25bc6d932f6af9eadec9ab4825895f5ea6edcb05","datavalue":{"value":{"entity-type":"item","numeric-id":4069780,"id":"Q4069780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$58AAE97A-292F-4A55-9C64-A0DF2E2101BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc0475b88b6c9f3d43c30c82d796f3e8ce41f978","datavalue":{"value":{"entity-type":"item","numeric-id":3219763,"id":"Q3219763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095663$AB070386-03F6-4C94-B017-10564118DE45","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec7b9528537832000ea6e3b85ffd07ee04134b68","datavalue":{"value":{"entity-type":"item","numeric-id":3123054,"id":"Q3123054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fe438aebb734d2db511d12b533009ea153e98f3","datavalue":{"value":{"amount":"+0.9379562","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$F034A576-E3DE-4BE0-8F14-82C99D9D5F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0abe835be3a70d6ab59bbbddf69b75f6de5ba08c","datavalue":{"value":{"entity-type":"item","numeric-id":4015003,"id":"Q4015003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3365fb3cfc0eb5d4d39b90490c881ecb2aebf549","datavalue":{"value":{"amount":"+0.9088529","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$876B2AEC-F55C-420C-B5B2-886D1C0BCE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f45e37955a7748c7988a9d2a01410e14a9542bb","datavalue":{"value":{"entity-type":"item","numeric-id":2503295,"id":"Q2503295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"038d1436a05610b0fdc72f43ad003e1c8edbeb33","datavalue":{"value":{"amount":"+0.9042834","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$7159CCCF-41CF-4980-8D97-62B0F71DF7F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8400a64cab3c7c323ef6b51bff99db05d64394e","datavalue":{"value":{"entity-type":"item","numeric-id":4638059,"id":"Q4638059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"721f677c6804714ea775cd7370cdf6845b70efca","datavalue":{"value":{"amount":"+0.90200734","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$C5E604DA-65F8-41FD-9BB5-2A365FC46FD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f160b2976fc5b252c2e956019b44c199e9b4b61","datavalue":{"value":{"entity-type":"item","numeric-id":4601837,"id":"Q4601837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32d093313088e31d4f42c3449b8fa21a0a70fb68","datavalue":{"value":{"amount":"+0.90119743","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$A54DD472-F078-4027-B900-AD4A53CE70ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ae355077babb907bb2783128a3f5c1e72ed2344","datavalue":{"value":{"entity-type":"item","numeric-id":4015974,"id":"Q4015974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1df44968b83c43da2bae619c2f04fc14112b841b","datavalue":{"value":{"amount":"+0.89873856","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$EC221DEE-D3B6-48D7-AF56-ADE8938F9D30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a818384b7effad5f0b8e6f908ba9fc52ac82cb1e","datavalue":{"value":{"entity-type":"item","numeric-id":4651502,"id":"Q4651502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9ea2efcaa1fd803e59aac6740165f3331d90920","datavalue":{"value":{"amount":"+0.89544845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$6E5AB460-5371-45EC-AC6E-A1E913F3697D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37caeae9a465b2769a0447d91a0efea13427a792","datavalue":{"value":{"entity-type":"item","numeric-id":3976040,"id":"Q3976040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"346695ecb3a51f64db7be6dfc8d55b33206aeac1","datavalue":{"value":{"amount":"+0.8948288","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$785BF3A9-7E6A-4F6E-9AE2-5D8F9A49E711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65ba63261300f459c94e83b4bd43ffd903676db6","datavalue":{"value":{"entity-type":"item","numeric-id":5368903,"id":"Q5368903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dd869e32ac8d1793bbe9fdd6894c47e934ff001","datavalue":{"value":{"amount":"+0.8935565","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$5272A2E1-5803-42E2-B5B9-A66885E53230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bed2ba016a85e80ae4a68d62d2b9670ed0398565","datavalue":{"value":{"entity-type":"item","numeric-id":1734694,"id":"Q1734694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57ab662b4079fde17cea4f89555ea636591a5203","datavalue":{"value":{"amount":"+0.8921422","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1095663$88629D69-D3B6-4588-B724-DC97240631FF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On solving hard problems by polynomial-size circuits","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_solving_hard_problems_by_polynomial-size_circuits"}}}}}