{"entities":{"Q1079364":{"pageid":1090116,"ns":120,"title":"Item:Q1079364","lastrevid":48961135,"modified":"2026-01-06T08:06:49Z","type":"item","id":"Q1079364","labels":{"en":{"language":"en","value":"Some remarks on witness functions for nonpolynomial and noncomplete sets in NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3963198"}},"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":"Q1079364$9A921FFD-7482-48CE-9510-3ABB234ED4D8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"78828814224dcd833cd6b41bf98b6a28a06adaa7","datavalue":{"value":{"text":"Some remarks on witness functions for nonpolynomial and noncomplete sets in NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1079364$774956F3-1BD5-4175-ABB3-AD1B50FCE32F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1f617bd4ab5af70099ba823c5b65277e36c31e44","datavalue":{"value":"0597.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079364$FED65795-01BA-4286-B965-C8693594317F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d9a8f45b77bda03eaa0587a2a826385d3f811a13","datavalue":{"value":"10.1016/0304-3975(85)90140-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079364$87CFCE85-3E36-4F58-A4F7-209758B1FF33","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$416F857B-7A89-420A-B848-BDA5D47DDD64","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$943D44D7-2C24-4411-9A71-6FCE909BEC19","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1079364$8B5235B0-A0F9-4698-809B-0B7E0B849F2E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ad649991081dca7bf8d94a513d465840c1bf49d2","datavalue":{"value":"http://digital.library.wisc.edu/1793/58504","type":"string"},"datatype":"url"},"type":"statement","id":"Q1079364$2E3DE512-ED9C-49D8-96B9-03381EB6338F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079364$CE4EF302-9B29-403E-AA36-025BEC9A67B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079364$7900618F-CCB4-44B6-9C63-2B203AD16158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079364$21A6E1B3-5BAE-4CC2-8BC8-C0FD2C4139DD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c304773cd7eff7bbf7cff56bef35c195f2e1d6be","datavalue":{"value":"3963198","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079364$3803D3DF-CD5C-49F8-BF41-791EE59EB15E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7aa281bbb7a4dc46607b4308456bcb94f1c02c2a","datavalue":{"value":"witness functions for sets in NP and coNP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079364$0D7B6802-CC56-447D-8889-F1862344925D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e6fef79d781284909ec93a485678c7408e58583","datavalue":{"value":"polynomially computable function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079364$5C6787F6-D1B1-4BB1-B7F6-BC5DD56C1959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18b896e4875df610358fccf59713481feead9685","datavalue":{"value":"NP-complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079364$9BDFD0DA-4CB4-4A83-A823-76DF0B1E6650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5867ec7b44aefc01672736513dfe6410a0300cd5","datavalue":{"value":"SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079364$3833AC9C-689C-4BFB-9FD4-1D240958E25B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41d9aedb6824d88ffdf97bd719a4fed2bb54c845","datavalue":{"value":"k-creative sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1079364$49D49AF7-3DBF-40FE-9178-97DB8566B071","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"137e6d050feda1476c9daf85494465b51d7884d8","datavalue":{"value":"Q56610696","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079364$27388DED-1361-47C4-820B-39BA172B9144","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":"Q1079364$BE76C1BD-922A-4887-9D80-6CF31A4C42E0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4fd81a4df178edf22def9c25f124d43c46b3ed11","datavalue":{"value":"W2008585307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1079364$329EF7FE-6E2A-4366-9844-C421EA1AC790","rank":"normal"}],"P223":[{"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":"Q1079364$6A05FB8A-3970-497C-A634-B3548F5D2129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9af52c66421185c07ca4d865efeb189c0dddc801","datavalue":{"value":{"entity-type":"item","numeric-id":1158964,"id":"Q1158964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$622C8822-E313-4739-BB8B-A66EA257348A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dae26af80a5696fa8c01db658b71f7ff80167bbe","datavalue":{"value":{"entity-type":"item","numeric-id":3248015,"id":"Q3248015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$64E54571-020D-429F-8207-615BC86AC199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06d0c58e682193b21b28b6f9ff7d6a7b9fbf894f","datavalue":{"value":{"entity-type":"item","numeric-id":795035,"id":"Q795035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$5A81B54D-8543-44C5-885C-A69C763C2A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3da510a58b16c0736f10bd517df8e982dda6dd9c","datavalue":{"value":{"entity-type":"item","numeric-id":3922170,"id":"Q3922170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$2BE39067-A46C-4AFC-BFC0-2BDC2C0F8C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40c62062de7837e74980976f9ffd2b1553f5599b","datavalue":{"value":{"entity-type":"item","numeric-id":1140080,"id":"Q1140080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$E6BEC17E-4909-42A4-88F2-CB4BEDB602D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$19B9B677-C5D8-4796-B1C5-A50551A50175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1b654d3d6b090646e55f1e1b7791b8d40e28fd6","datavalue":{"value":{"entity-type":"item","numeric-id":4198487,"id":"Q4198487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$6A5D4A45-F732-49DC-A5F1-A87CEB2DAC24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"917800fa52c098f2382f946c4094dc39e957bfbe","datavalue":{"value":{"entity-type":"item","numeric-id":4153600,"id":"Q4153600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$0156B829-7330-4FF4-8D29-B0471368A054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c19040a60a44db62995cb08427466942d64d95f5","datavalue":{"value":{"entity-type":"item","numeric-id":1077412,"id":"Q1077412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$59FCF919-C01E-4EA3-A322-A4D501456E35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"850ec53483c087fa2e8890fc924e571da7793c17","datavalue":{"value":{"entity-type":"item","numeric-id":3232283,"id":"Q3232283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$E167F746-FAA5-4E5C-9F78-7EEAEF95B845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01fc2040ffe16ed03fdd5700cb1de1e73a3cea54","datavalue":{"value":{"entity-type":"item","numeric-id":3787474,"id":"Q3787474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$589CA832-1804-4B27-A722-3A2D235E130A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$BEAE46FC-BA49-40E0-916E-40AB8CACC922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62decd6aef1b530104bc159f5e2acd57c4acfc08","datavalue":{"value":{"entity-type":"item","numeric-id":4075448,"id":"Q4075448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$7ED171A9-0EFE-4708-BDB9-3F7FF31901D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cefd7574d6776aa0391d0dd90bd375c1811d3f9","datavalue":{"value":{"entity-type":"item","numeric-id":1164414,"id":"Q1164414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1079364$B7CEAC60-F6BB-4E4C-BD29-13DB222199DC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3588b73cc8b4751cef053e43842b7cc72506545b","datavalue":{"value":{"entity-type":"item","numeric-id":4895816,"id":"Q4895816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfe28236ec4a625822c0c705204415b00f02bd41","datavalue":{"value":{"amount":"+0.8093357682228088","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":"Q1079364$6B6D1063-A05C-40BB-A5E1-F476A8F8A08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"541e3ef8a055802d800489c2541893e9a84474d1","datavalue":{"value":{"entity-type":"item","numeric-id":1097694,"id":"Q1097694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e35d56e86f62116251724fde04bd15c0cc167515","datavalue":{"value":{"amount":"+0.8050334453582764","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":"Q1079364$DC4A4C0A-E2D6-4C7F-B11C-9C395583B667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"622f2916f54ea25b4ffc040e4dfa93312e6a0c2f","datavalue":{"value":{"entity-type":"item","numeric-id":1183565,"id":"Q1183565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb9f4c5b390dbf3f0d067cff7f305fc44a58c253","datavalue":{"value":{"amount":"+0.7992414832115173","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":"Q1079364$7350F527-1C68-45D9-87D3-20F5118A775A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22789724458e4876f1dafaac56a6e6d701b202e2","datavalue":{"value":{"entity-type":"item","numeric-id":4327382,"id":"Q4327382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca53bc4d247eafb704053a73d8aaffa78189cc61","datavalue":{"value":{"amount":"+0.7954776287078857","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":"Q1079364$10C07B08-815D-40BD-BC36-BAC7EBD6D591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b822841fddea48e0f0de298194ea8afa91f1652","datavalue":{"value":{"entity-type":"item","numeric-id":3026341,"id":"Q3026341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3041fba7d112585b5deec63a0b0153ae4b10485e","datavalue":{"value":{"amount":"+0.794353187084198","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":"Q1079364$3338D683-6A3C-43E6-A114-CE8322A6649F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1079364","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1079364"}}}}}