{"entities":{"Q3335768":{"pageid":3346476,"ns":120,"title":"Item:Q3335768","lastrevid":48730348,"modified":"2026-01-05T17:50:23Z","type":"item","id":"Q3335768","labels":{"en":{"language":"en","value":"On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3867309"}},"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":"Q3335768$0B3B7B62-B07E-4F17-A2A2-1291DC6E60AC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a4cab7a474ac133f46e0c49e34e3389675348891","datavalue":{"value":{"text":"On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3335768$1797B4E4-3653-46EB-9906-4B2A30F762C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"141c9e43d1c6c4ad8be590e278906c2fc10a71db","datavalue":{"value":"0545.03023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$0E2B3FE9-8986-4480-AB9E-C78AB88AC2D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"08547ce675322e1b581928ad5644fb9c01d67d9f","datavalue":{"value":"10.1137/0212027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$CCCA2A66-9A23-4B16-9CE8-2C1E8FD6F77A","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":"Q3335768$A8C125C4-4B6E-44E1-94C9-AEF52BD7CE36","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q3335768$2620B3D4-D35F-4B5F-9392-773510353183","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$CE4C579C-4302-4B98-979E-5EE0D1FDFC35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$E02D940B-EC95-4447-B515-8736B4AB0ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$85474A7C-E9B8-4D63-BE56-ABD17863EE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$BA7BD0CE-F885-4BE2-A045-3857F4C60128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$1540783F-C705-4D47-86E0-A6BA695ADB89","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"32479105be39cb9543fcab020d543620cc17e7e8","datavalue":{"value":"3867309","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$74DDF090-9CC2-49D9-91FA-38E602C0E07F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18b896e4875df610358fccf59713481feead9685","datavalue":{"value":"NP-complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q3335768$FBB422C9-8537-438F-B222-27133D891BF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ca57d225358d55c161d2fd9284b1f4649a91fc4","datavalue":{"value":"polynomial-time reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q3335768$89509019-380A-4AFF-A62B-C963909A3C54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"214cfd74473bc6d0eae3b8ca28189646d43fd7f1","datavalue":{"value":"many-one reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q3335768$C6CDE8E7-F254-4B09-9622-867FB5F22633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d4e15085277c77e1f6537f1355f78224cb0f64","datavalue":{"value":"truth-table reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q3335768$5EA686E1-BF10-411F-82D5-D7745E054FAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2489cf279a30c5012a34c55fe90738877025e05","datavalue":{"value":"coNP-hard set","type":"string"},"datatype":"string"},"type":"statement","id":"Q3335768$46EF869A-5627-493F-ADF6-F60BB6E11324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad43bcd34d069e6f3c71d7afa37e29d215fd1b15","datavalue":{"value":"sparse set","type":"string"},"datatype":"string"},"type":"statement","id":"Q3335768$25B000CB-8724-4211-99BD-C9E86EF0ECF8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9859a4dcc00fc8d1566f43eb1abbd6d402c90633","datavalue":{"value":{"entity-type":"item","numeric-id":751803,"id":"Q751803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3335768$9A76C00B-44E0-4B33-9A63-E98666EC9C4B","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":"Q3335768$9F09301B-44FC-4F81-BB90-EF3BB237EFE3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dbb56ca4a53e490dc12e4692799d063b9bbd9922","datavalue":{"value":"https://doi.org/10.1137/0212027","type":"string"},"datatype":"url"},"type":"statement","id":"Q3335768$C1901317-7936-4232-ADA7-FA0EDF7A0A34","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1eb7c96f83c75776808ef7d87bf357a8e9162e7c","datavalue":{"value":"W1986448430","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3335768$6AF15851-EDB6-489F-BCB3-98A14CAB82B9","rank":"normal"}],"P1643":[{"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":"5e9ff572e85dc3d5e350c138f562c4054d3e73c1","datavalue":{"value":{"amount":"+0.93475741147995","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":"Q3335768$02A9A855-DBCF-43C8-A3D3-BA18A0506BCE","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":"9bd32011c1e5089b48b3a3653513e347904321a4","datavalue":{"value":{"amount":"+0.9268470406532288","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":"Q3335768$55F069AB-53AB-4DE7-B9C9-2E060E6C73BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ebe20fcf0733352aef95a520a87c30e5dd8162a","datavalue":{"value":{"entity-type":"item","numeric-id":1329162,"id":"Q1329162"},"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":"Q3335768$DF3F4A89-B48F-4A10-B7C8-329C07D44453","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":"1263fb7a18d31d59dedbdfa178c485f3ce6fc6ed","datavalue":{"value":{"amount":"+0.9048526883125304","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":"Q3335768$03A7AD9A-F7CA-403C-A9C5-5FEBD1834C25","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":"68c152b76277780cec0735a1475d20426a135551","datavalue":{"value":{"amount":"+0.9046558737754822","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":"Q3335768$10A30052-C4D0-4EEB-A1DC-A2F854FFB2CB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3335768","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3335768"}}}}}