{"entities":{"Q3978778":{"pageid":6008668,"ns":120,"title":"Item:Q3978778","lastrevid":46240861,"modified":"2025-12-24T09:26:39Z","type":"item","id":"Q3978778","labels":{"en":{"language":"en","value":"Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 12898"}},"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":"Q3978778$EB6F776A-998E-4456-B6D6-A358E6070755","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"89251fce58ae9b6e5c0818d1fead526470347cf7","datavalue":{"value":{"text":"Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3978778$E4E92413-20B1-4F88-BFBD-B9B3B3D5654A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68db7de91c6f942bedc30ff43d19234487bb7dee","datavalue":{"value":"0741.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3978778$AD05D2ED-B89E-45FA-8ACF-487320129DA1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"da00f297247415a22dd6c85f056d5712f6c918aa","datavalue":{"value":"10.1137/0220030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3978778$44DF718A-2BC9-44CD-80A5-F4E623645AC0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc6e6bd68ab9bdc466808c1af936ab0e954ebc97","datavalue":{"value":{"entity-type":"item","numeric-id":1210292,"id":"Q1210292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3978778$252D81EF-2541-4C4C-82C6-195D221E62D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9977966a206c32ef4456e9d3d93668d79c9cf98","datavalue":{"value":{"entity-type":"item","numeric-id":354651,"id":"Q354651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3978778$3CD7237C-9221-4855-A2B6-FABD9CCDCD42","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3978778$7FFE0F21-827B-4935-B235-9D9E9EE25688","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3978778$9BE3440C-8001-4EF6-B5D5-92A6DDB2FC5D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3978778$16A95CEB-DA2A-4F8F-92AB-2EE5F6126A9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3978778$E6CB5130-2F27-49CF-AB3E-19C046C0F54D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3978778$81E74146-D435-4326-B732-321612BC2146","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bbabe8caa9303bbe21400032b7a39cff25b7d375","datavalue":{"value":"12898","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3978778$3850114A-9D06-4576-9A86-F92C8B37CF5D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9cad7b911d53167783a84ac338f14829e93d3cc7","datavalue":{"value":"Berman-Hartmanis conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q3978778$8AC57515-10DF-496D-BA99-E75DE51CF45D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bf27ad478dccffc260d084ffb53cdd6f4d2b3db","datavalue":{"value":"polynomial-time hard sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q3978778$9C20F7E6-838B-41AF-96B9-39B245C799C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70d52ace7a2b142f90cb2af2e4a76e639ac8fe48","datavalue":{"value":"sparse sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q3978778$B40AC3C4-6DAA-479A-803D-9186E39B855C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af6f985816b877ee30ebb6a2ce762085c8ec817e","datavalue":{"value":"bounded truth-table reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q3978778$5036273D-855E-42E5-BA47-DDC9DC9DF4B1","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":"Q3978778$05803F2F-D5FA-4D6E-988A-62BE6A25B37F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5e7e19dd510399cd75c6af49466b1c353a8cfceb","datavalue":{"value":"https://doi.org/10.1137/0220030","type":"string"},"datatype":"url"},"type":"statement","id":"Q3978778$6E46DAF9-2D8E-48D0-A9C1-C1F140A29466","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9dd7de2046641ee96ba7c0c930800646072cdbed","datavalue":{"value":"W2039334189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3978778$F757D51A-301B-41F4-A8CA-B4CE445B1D42","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c2adc893ba0e353cc07a8405075284e7651ff53","datavalue":{"value":{"entity-type":"item","numeric-id":3335768,"id":"Q3335768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0a14f8b41acaf7ff02b4c5628b4428717a0bafa","datavalue":{"value":{"amount":"+0.9223230481147766","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":"Q3978778$CE4A9D1C-B33F-4652-8223-000C9E8F2202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"869d56623888063310bf39732f2ef74584b45b2c","datavalue":{"value":{"entity-type":"item","numeric-id":1191028,"id":"Q1191028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ce2214a4d71885d7fcaefe6179f4cb287d2af9d","datavalue":{"value":{"amount":"+0.8992949724197388","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":"Q3978778$4F7407CA-8C28-4CFE-A126-F41B4936C4C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d2c6b00319aebd8229b2a325bdd25c903fad5ba","datavalue":{"value":{"entity-type":"item","numeric-id":3314997,"id":"Q3314997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1e960dd1a42bb202ac0a261151768329f7be09e","datavalue":{"value":{"amount":"+0.8911082148551941","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":"Q3978778$371D0F23-012E-4608-99FC-69822E6BA709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b09f64724988c7a029e89b27b72c75acb7a8bf5","datavalue":{"value":{"entity-type":"item","numeric-id":3816983,"id":"Q3816983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b57bf8f327792daa937443f05b683f9e5cf5033","datavalue":{"value":{"amount":"+0.8898025751113892","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":"Q3978778$05CFDD18-AF7C-490E-AFFA-8BD0795C43D0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3978778","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3978778"}}}}}