{"entities":{"Q1109568":{"pageid":1120317,"ns":120,"title":"Item:Q1109568","lastrevid":49210039,"modified":"2026-01-06T18:47:18Z","type":"item","id":"Q1109568","labels":{"en":{"language":"en","value":"Promise problems complete for complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070316"}},"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":"Q1109568$8FE090AB-49F7-49C2-9021-F526EFB54C27","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6cd637e1a4ba6aadfd7b4a012c6afdf022011f24","datavalue":{"value":{"text":"Promise problems complete for complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109568$3C3CFAB4-A79E-4436-9F0B-3C668809A650","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f175ec7ad8e507ea95e8fd2d3ec9883e5bdd0c9","datavalue":{"value":"0655.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109568$792CC554-946A-456A-AA7E-02A0F2132BE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8af59828e3400b9a3db360b955bf16737614913b","datavalue":{"value":"10.1016/0890-5401(88)90030-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109568$A9A3CFF3-1BF3-4983-B0E1-CD46F565FE41","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$B22E8D7A-66AC-4AE5-999A-141D5E90AE5C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1109568$7DF2B683-CC38-4E47-A293-7FA6DC482F16","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109568$41FBEA8A-3D61-401C-945C-BCB7F75CC680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109568$41A04588-350F-4C94-AC8F-AC4EE0D31700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109568$B7880BBB-FE18-42DB-8389-33CC35148D85","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bc729350c9ffa592c659b0cf8fe640cc60f65c18","datavalue":{"value":"4070316","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109568$7833492C-111A-4202-A245-326DF33DC4D9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b705aa46cd1219cbdbb9c44f00c98c6ef5e9a5e","datavalue":{"value":"hardness results","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109568$73022B64-6FDA-4E58-A744-5BA576C2B896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7284c8089fb80d066c5816f5a3852a61f6cd9acc","datavalue":{"value":"promise problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109568$23EAF23A-EDF4-4BE5-93F5-5E6CDFFD42DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3412d920104b4c87c247903b9eff19e9c44b1702","datavalue":{"value":"self-reducible decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109568$3CAEF13F-346C-4ED2-AAE0-8C74D329BD8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109568$E552CC43-3D0D-4679-9505-06252CD524B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"29b02350197f27ae1879c4b07e2f60550fcfbf54","datavalue":{"value":{"entity-type":"item","numeric-id":161380,"id":"Q161380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$E2FB2224-C1A4-4882-9944-99874EDBCE9A","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":"Q1109568$F51D125F-4D5B-4E7C-A00B-AFA400326FB8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4660edb533bb130b9143e5d40362ad42c3be9b2c","datavalue":{"value":"https://doi.org/10.1016/0890-5401(88)90030-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109568$A349CC6F-8364-4FEE-ADDA-2518BD44B2CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"09e6aa7674d9bfb1867f35bbafa2f6c45d6c5f29","datavalue":{"value":"W2066390433","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109568$17F4060F-1362-40A4-8BDD-FD0DC02D5D3D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"10b01d0fd1093fe05a5773fadd6469a44f83255c","datavalue":{"value":{"entity-type":"item","numeric-id":1227731,"id":"Q1227731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$8DC1676D-7D78-4D4E-9D97-C60649944658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49ee1410bd306d6722cc2c176479c826bbb0715d","datavalue":{"value":{"entity-type":"item","numeric-id":3722415,"id":"Q3722415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$296D6F9C-1867-47E1-9B9D-BA9108D16571","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d8481b383524bbb1d42d352020c18ea39581b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3888962,"id":"Q3888962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$63828AC0-6299-44B8-BE9D-FCA89765AC56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$273AD138-8A88-4382-BD37-E5C1D73C2BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b93f8e116857da1c2d9e0d6cc4d460b9a69e44f","datavalue":{"value":{"entity-type":"item","numeric-id":3328286,"id":"Q3328286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$C300B81B-8D14-42E6-AC33-B9439F7F263C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$DB47D7DB-162A-45E6-B407-51466C9CB1B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16983ec90d90b9bc0cf9374a8b751aa166b818e","datavalue":{"value":{"entity-type":"item","numeric-id":3769965,"id":"Q3769965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$15DD3218-154F-484E-84A1-FA8116E61736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6bef531e3c54b91b631aa952c0ca63f0ac7db19","datavalue":{"value":{"entity-type":"item","numeric-id":1054475,"id":"Q1054475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$3F3245EC-D007-4C4D-B852-544BE9A04350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$3D690125-77FB-4543-8B3C-0BB33E338996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37bd93f050a29505d9954e41ab03268b153e49a7","datavalue":{"value":{"entity-type":"item","numeric-id":4190619,"id":"Q4190619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$1278D045-4404-4A0E-B669-99406191BE34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d18e4b439adfecff09b2cf1367d09302baaa3617","datavalue":{"value":{"entity-type":"item","numeric-id":4739905,"id":"Q4739905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$DC6565F7-96DA-422F-A9FD-008F581287C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd520b49bc58e84d7c227fcb0bc974b432f91cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1166515,"id":"Q1166515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$77536C43-ACCD-4AFD-9350-023D394358E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cacefeedbc112be8dbe48f89e8cd3c176bb87a52","datavalue":{"value":{"entity-type":"item","numeric-id":3816974,"id":"Q3816974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$D8DE99EB-4540-4110-9EE8-7DCA7A945C2F","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":"Q1109568$029CD178-2263-4751-8799-47F55FE23D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b10c99d5ba9164e3ec4889da522a3cf32a4074ce","datavalue":{"value":{"entity-type":"item","numeric-id":3659676,"id":"Q3659676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$10EC2AF7-2539-4707-9355-B705C453F4C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109568$16CF5FAD-C400-4B52-91D7-EFFE5F88D8F0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"808b70f408b84029ae247f92dac9fd822945ea18","datavalue":{"value":{"entity-type":"item","numeric-id":3975932,"id":"Q3975932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b28ec219f34481e24ca82d0051eee3b5f21fb363","datavalue":{"value":{"amount":"+0.8671085834503174","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":"Q1109568$758F57A1-19D3-460D-BA4F-999C18BEFE94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"093c4723104c7c5c7ba6628a88a66a7344026964","datavalue":{"value":{"entity-type":"item","numeric-id":3107337,"id":"Q3107337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9458bdb2b74ff2b06c763aa1acd1d6a4bb98ef31","datavalue":{"value":{"amount":"+0.8635587096214294","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":"Q1109568$51D92870-C6CB-4AA3-B303-7723C950A385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d6d35347cfbece5c7d7a03d072b5a07f6b39857","datavalue":{"value":{"entity-type":"item","numeric-id":3722415,"id":"Q3722415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76180ebae12f10002819c3e68e76e26e5d8df242","datavalue":{"value":{"amount":"+0.8174023032188416","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":"Q1109568$0B86C22E-BFB8-4744-BB04-BCC9728DBE63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f73a2f614914ac732f7283bda95dff7d1861ee9","datavalue":{"value":{"entity-type":"item","numeric-id":4877117,"id":"Q4877117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"656b7651f3dc3ce6ac46144bfaffac00440af3f2","datavalue":{"value":{"amount":"+0.8134713768959045","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":"Q1109568$2317343F-B570-4036-8E3C-4131ADE8A398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2562826fd12df13e4c81cc5fdc25503ab46fbed6","datavalue":{"value":{"entity-type":"item","numeric-id":1398371,"id":"Q1398371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"656b7651f3dc3ce6ac46144bfaffac00440af3f2","datavalue":{"value":{"amount":"+0.8134713768959045","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":"Q1109568$526502B5-B2E4-4A44-9377-BDA35ED3F48A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1109568","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1109568"}}}}}