{"entities":{"Q1276171":{"pageid":1286921,"ns":120,"title":"Item:Q1276171","lastrevid":70543710,"modified":"2026-04-13T15:21:18Z","type":"item","id":"Q1276171","labels":{"en":{"language":"en","value":"Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1240651"}},"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":"Q1276171$81D0BEF6-9042-43FD-BD74-1DE2F85DE429","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"434a5c9a1304810f92dbcca679d58938ddd069ea","datavalue":{"value":{"text":"Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1276171$95146233-8400-4EEA-9B7D-7D44A8DA9EC2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"94f4519cd81c635ce9eb8da504f86b1fe8852f9d","datavalue":{"value":"0921.68030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1276171$CC256954-BC4D-4BAA-9C9C-27459947DC5E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a25d963ba8459ff509d0f0ec3595c17b9f7f836","datavalue":{"value":{"entity-type":"item","numeric-id":354650,"id":"Q354650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$6DED54BD-0902-4ABC-8691-266F081FC140","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$8193FF62-B46F-4A6A-9A96-9A73C3D1529B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a2f08d963c55f4abeb9c13704872e9f590d65482","datavalue":{"value":{"time":"+1999-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1276171$FC7287D3-081C-4B7C-A4A9-B54FE44AAAE6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6a8c73c5068cbf7bd7274e17f0b836799694c21f","datavalue":{"value":"https://semanticscholar.org/paper/8cdc3d2342e6b56553b96aaeb58386652dd791a5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1276171$2DD9860B-618C-4E27-A131-64AA36D3E8CC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1276171$6678B31C-820D-441B-B33B-5C4D4C8A097A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b973340e366320a299325f7aa9a90744fe3912d4","datavalue":{"value":"1240651","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1276171$F8A587FF-CB5F-45CB-AA03-AE870A1D4072","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bd3847b762cf2876b559c75dfad41e1cdfc9c94","datavalue":{"value":"sparse hard set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1276171$2770303B-29E9-4EF9-9B62-62ACCEC1381C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8c3f127e27aaa2afe7e371658082dca13cac7a7","datavalue":{"value":"truth-table reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1276171$9487AE4D-431C-4B79-B155-610CB5088D55","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":"Q1276171$674BC99A-9A68-4D89-88E5-6CBA68A57908","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"892cfea13b6d4c795bf60ad39502cc0680365da0","datavalue":{"value":"W2003299480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1276171$B575806C-AF1F-4047-82A7-CA26D6273D5F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae99a378a38b16b74a1ce201fcf4653f66b95edc","datavalue":{"value":{"entity-type":"item","numeric-id":4256649,"id":"Q4256649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$25F0489A-B8BF-4D28-A51F-3FB24C0054DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e0a936d29cdb004405e9ceab9ae0698c1fa987d","datavalue":{"value":{"entity-type":"item","numeric-id":4321931,"id":"Q4321931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$8E0CE5E5-E857-4C5B-A102-10E16CFA95F2","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":"Q1276171$BCDBFFD9-2BB8-4F99-A5D3-EF5409440E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a6b13b2ba37a9810801d8784e6422607a5338cc","datavalue":{"value":{"entity-type":"item","numeric-id":4745254,"id":"Q4745254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$C083D7AA-3C01-4B4E-8F47-C26D3E7641C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a3c50b8af8c54451fefb93a249d1571c6fe9d0c","datavalue":{"value":{"entity-type":"item","numeric-id":4593941,"id":"Q4593941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$2F8C8B84-E49E-4129-9163-1461F1C905DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e10f4068542676ddaf663d1619987e5731b7f56a","datavalue":{"value":{"entity-type":"item","numeric-id":4252721,"id":"Q4252721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$1C298283-F087-41A1-B5A8-DE971482B876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$80E3258E-BED0-413E-AF5B-B6D440F76639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b23a99da8df474d603cdef7b4c76229f6a312c3","datavalue":{"value":{"entity-type":"item","numeric-id":3787477,"id":"Q3787477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$A939A2C8-9A9C-4983-9153-6A46108043CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d31b9fbcf5b103d19429f8ba43bde08b37cbb29d","datavalue":{"value":{"entity-type":"item","numeric-id":3470109,"id":"Q3470109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$C0CE8E43-EC03-4E0B-8EC9-CD5B25CDE010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"891f00d58aa1508cdc3fb80ddfb5ae33a36d09d7","datavalue":{"value":{"entity-type":"item","numeric-id":1249940,"id":"Q1249940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$844FB92D-3232-466C-9C27-9C33CB112CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88d0a24cc068497b64840a59e20b0d44433bda0b","datavalue":{"value":{"entity-type":"item","numeric-id":1329162,"id":"Q1329162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1276171$5CB002C9-CF90-450E-8008-273A416F73FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4179e4af0cf1642e8f9e0107af9c5c6a5d44dffa","datavalue":{"value":"10.1006/JCSS.1998.1589","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1276171$2A57DA4E-E33A-4F47-AF9D-26E9E1FC3C2B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5e47ad9b1c4b268ecf6d907bf96f5585038df15","datavalue":{"value":{"entity-type":"item","numeric-id":4593941,"id":"Q4593941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7def3be561c782f51dce29a061467451f838d995","datavalue":{"value":{"amount":"+0.9085765480995178","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":"Q1276171$339ABAA1-430A-43C9-B981-846C74AFE8D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ce60a7b12a52d81f977c6807db10402fac1fae8","datavalue":{"value":{"entity-type":"item","numeric-id":4256649,"id":"Q4256649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"487cbb9cc558adf95e86454ebe47bd0e6e047a8d","datavalue":{"value":{"amount":"+0.9034624695777892","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":"Q1276171$A3F689F3-219E-4B7C-B1AB-D1A5CAB3172E","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":"b918ddc6b0a6e09bb8d625c8719a09ab239f05ca","datavalue":{"value":{"amount":"+0.8686792254447937","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":"Q1276171$10E5E338-DAFA-42F6-B487-925372E46633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"416225fa01e39a8ebf2f3d357d8d57a05f109b4f","datavalue":{"value":{"entity-type":"item","numeric-id":3978778,"id":"Q3978778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4593cd4572bb074f30a1b97f61115a91ed019d00","datavalue":{"value":{"amount":"+0.8636769652366638","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":"Q1276171$6FEC0E51-3C7A-4BFA-9CC0-734C84C9DAD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets","badges":[]}}}}}