{"entities":{"Q1097692":{"pageid":1108444,"ns":120,"title":"Item:Q1097692","lastrevid":69635130,"modified":"2026-04-13T08:21:21Z","type":"item","id":"Q1097692","labels":{"en":{"language":"en","value":"A comparison of polynomial time completeness notions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035136"}},"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":"Q1097692$7C20DBFF-88F1-4825-B89E-B4B673CFD450","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6b621d0c28aa900a031ae810a8f57512c36eecff","datavalue":{"value":{"text":"A comparison of polynomial time completeness notions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097692$5F57AD65-2CA3-46F0-853F-D891B5878DC5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d12acc05d8b7b24da2f57e728c4c6c464fa9ac80","datavalue":{"value":"0635.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097692$869A8977-C45B-4B83-ACF0-463D43C8F3CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ce88f2d9e645ecd5e6717d20901d2aeec0976979","datavalue":{"value":"10.1016/0304-3975(87)90132-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097692$15EB4683-D230-4AB4-A1C8-96F05505028E","rank":"normal"}],"P16":[{"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":"Q1097692$C8A8699C-8C0C-4AEA-BA12-FE69C9002113","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":"Q1097692$2908A149-859E-4411-9CBC-AF0CF93BFF92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1097692$4E8B0F79-A26F-426E-889F-2CA091B641F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c0db6436c10c7a876dff6069b68dc2e4a051c75b","datavalue":{"value":"Several types of polynomial time reductions for the superpolynomial decision problem class \\(DEXT=\\cup \\{DTIME(2^{cn})|\\) \\(c>0\\}\\) are considered. The purpose of the paper is to characterize the differences between polynomial time completeness notions for DEXT with respect to any pair of the above reductions. The author succeeds to prove all but two differences for the class DEXT. An interesting open problem is whether or not the obtained results hold also for complexity classes specified by nondeterministic machines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097692$12249B13-EBDD-42C9-A40F-9D337AE4CF07","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097692$6F3335ED-AA24-41B8-A1E4-BD28EB0361A3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca25a929dd718917e4e249d123b3da91ad048c96","datavalue":{"value":"4035136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097692$8B955B0D-A3BB-423C-86BB-738934563A0F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5306a70bce69e1022857fa6d89b3ef488725dc93","datavalue":{"value":"polynomial time transformation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097692$12F8FD11-BDCF-4094-8488-F64EF77FF1A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d9be98d0d23b8f354e206eba7b1fa68829f4ac6","datavalue":{"value":"superpolynomial deterministic classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097692$239CE88E-AF51-45F9-8453-27DFC20C16C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58b53a0aacc5e04758fcfd7a6dea838ea79f8792","datavalue":{"value":"polynomial time reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097692$2812577D-A323-444B-9CD5-14CE207BE036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"111c648c4d8c5f0ad609d41ed118e4425a995ac8","datavalue":{"value":"superpolynomial decision problem class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097692$2B62DA33-A48A-4A94-9A01-0BBDB7EA5C0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6816fdf79dd11ac09d9af4886c02baab03d2cf9","datavalue":{"value":"completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097692$6E0E17EB-11ED-42B5-B272-C713C269714F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097692$1BED0755-AE1F-437B-BF24-7F61DD5F0EA8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9da44cf54fb523ec7773d0b3b496a66fdb2cbb97","datavalue":{"value":"Q56387788","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097692$3AFC9D9D-87A8-41FB-87F5-179DEF86098A","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":"Q1097692$E81442EE-E49A-46C8-B047-273DD2C0AB0E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a6a49c58397f69f8528bf6c19eb1a2700d9a9835","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90132-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097692$03E8B0E3-C467-4D14-9DDE-B7DD5A5124C3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4b57d892445d37b6638e19e690ef8f052ed3664c","datavalue":{"value":"W2068655609","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097692$A409F8D0-39B1-44D4-844A-427F9765668B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097692$DCC20DBC-24D0-432F-9C37-4DB85D71909B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097692$BB6D187B-2BCF-4F6B-A8BE-5685E4231340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097692$59DF3D82-E977-4701-AC73-B0C1A22DA7E8","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":"Q1097692$9910B39D-1307-4A69-8F07-3461F0B6A3FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37c3ecf6bbb80d30a5d10d29d6b817116fc55217","datavalue":{"value":{"entity-type":"item","numeric-id":1061119,"id":"Q1061119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097692$A1784EF1-0DE9-49A9-A1EB-5F8A6D8BB775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097692$C5E16D67-C20A-4417-8F69-DE1127889063","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef9791f4b37ee125203fd0d0075552c144cb2e86","datavalue":{"value":{"entity-type":"item","numeric-id":4162663,"id":"Q4162663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097692$E2272178-FC1C-41E2-84BB-ABD50B1D902D","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":"Q1097692$83A14A69-8C24-4A07-9DEC-ED668E8AADFF","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":"Q1097692$582245C0-ACAD-4676-B3B0-58DABBCB8E03","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":"Q1097692$FE9D93E1-4538-4E94-83CC-7D5AB410C0AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097692$66BCDCF2-19DB-40C8-B9A5-F6D0A5BC26EC","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":"Q1097692$659AA93A-8BFC-4E5E-80A9-57BC904A5902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f17a7f319117d5a44769bf519f74a5e5ddbffa2f","datavalue":{"value":{"entity-type":"item","numeric-id":1068536,"id":"Q1068536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097692$B3FFED3B-FECE-4C6F-B21F-55CD8604F04D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7024b584150a2e1ba8672fba00213125bc7194de","datavalue":{"value":{"entity-type":"item","numeric-id":4016403,"id":"Q4016403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d561470a49d65d7ed6fa5fa379867ce3cbd3f5b4","datavalue":{"value":{"amount":"+0.7758678793907166","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":"Q1097692$3C7B3568-6037-4A95-968A-1AB77CF1322F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3df135062f7e50c8769a5df902f0a2f39d6f36b4","datavalue":{"value":{"entity-type":"item","numeric-id":3979608,"id":"Q3979608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f04c9cb5fe59d4980e7a32bd6d88f02dab5a304d","datavalue":{"value":{"amount":"+0.7746209502220154","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":"Q1097692$B13EE81E-2728-4BD6-A0C2-0B5A93C37334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8273181031919cc5ee9ed42b01d671c50eac338","datavalue":{"value":{"entity-type":"item","numeric-id":1193869,"id":"Q1193869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9567d78e7da7a06bd20c0ef7e309ba1ebab6e171","datavalue":{"value":{"amount":"+0.7735469937324524","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":"Q1097692$9C737E27-94EA-426D-8768-25E9B34846A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"172d1e6ca7ad078485e2353069fd5faac7b01e7d","datavalue":{"value":{"entity-type":"item","numeric-id":4035688,"id":"Q4035688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2e58267d68e4a69cb09468bdd67ade7585a40c8","datavalue":{"value":{"amount":"+0.7708685398101807","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":"Q1097692$CFCA2238-313B-4917-B528-7095EABD7307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4ba55afd5bdd4ddd5808625e2678ba7c445825b","datavalue":{"value":{"entity-type":"item","numeric-id":4218121,"id":"Q4218121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2e58267d68e4a69cb09468bdd67ade7585a40c8","datavalue":{"value":{"amount":"+0.7708685398101807","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":"Q1097692$54EFFAA8-E286-41D8-974D-86570002BAFE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A comparison of polynomial time completeness notions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_comparison_of_polynomial_time_completeness_notions"}}}}}