{"entities":{"Q1068536":{"pageid":1079288,"ns":120,"title":"Item:Q1068536","lastrevid":66205725,"modified":"2026-04-12T08:15:12Z","type":"item","id":"Q1068536","labels":{"en":{"language":"en","value":"On one-one polynomial time equivalence relations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3932386"}},"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":"Q1068536$F370C142-4AAB-4973-A61D-07807F3B105E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3eff04eaaa8de2e93249427626f5a7d897f358b1","datavalue":{"value":{"text":"On one-one polynomial time equivalence relations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068536$687C52F0-1485-4EC1-86D5-71F29042513B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2500923d7fb9b97d76243c2b720dede3379b04a9","datavalue":{"value":"0582.68016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068536$FF16675A-E644-454A-897A-76623F4B3F0B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f69747604b58c9886acc2e99e8aa93e5885bebfe","datavalue":{"value":"10.1016/0304-3975(85)90218-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068536$3748DAE2-DDE2-46F6-967C-A50A60E4A703","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":"Q1068536$B8A32A26-52A3-45CA-A8EC-B2A2C62FD68C","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":"Q1068536$1A6AC455-B88B-45D7-BDDC-26B448905EFE","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":"Q1068536$4E2EADE0-A246-43D9-88E8-0C9FE41314AD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a7b577039196d371037357e3a6aeba3bdaf1ca4f","datavalue":{"value":"Two sets A and B are said to be p-isomorphic (A\\(\\equiv B)\\) if there is a bijection f such that f and \\(f^{-1}\\) are polynomial time one-one reductions from A to B and from B to A, respectively, and to be pseudo p- isomorphic \\((A\\equiv_ pB)\\) if there are polynomial time length increasing one-one reductions from A to B and from B to A. \\textit{L. Berman} and \\textit{J. Hartmanis} [SIAM J. Comput. 6, 305-322 (1977; Zbl 0356.68059)] conjectured that all NP-complete (EXPTIME-complete or PTAPE- complete) sets are p-isomorphic, and showed that if \\(A\\equiv_ pB\\) by invertible reductions then \\(A\\equiv B.\\)    In this paper it is proved that all EXPTIME-complete sets are pseudo p- isomorphic. So it follows that if the inverse of each length increasing polynomial time injection is polynomial time computable then all EXPTIME- complete sets are p-isomorphic. This result is also extended to many complexity classes, for example, k-SUBEXPTIME and DTAPE(S(n)), where \\(k>0\\) and S(n) is a tape constructible function with \\(S(n)>p(n)\\) for almost all n and for any polynomial p(n). In addition, this paper gives some nontrivial examples in EXPTIME-P which show the difference between one-one and many-one polynomial time equivalence relations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068536$D2F657AA-7993-4CCB-9967-DE487674BD74","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068536$B55D9D10-4644-4DEB-9E20-2D315F64B14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068536$C9101958-6F35-40DF-AD7D-86C674667252","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bc75e36dc76e538b92a0b06a7b0152c7e99aac35","datavalue":{"value":"3932386","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068536$D8F16B26-3618-4E8A-B857-93E0192EDEEE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83ad2c7d026a8a0a94ebf8e34365dd83894491d2","datavalue":{"value":"p-isomorphic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068536$47870CAE-5EF0-41B8-B878-44657632085B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7ad7e527e815dbc07cf8b18ca67548bbf176a4f","datavalue":{"value":"polynomial time one-one reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068536$8AD30120-C306-4CA2-8E7E-2948A458A408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7366df165c046bc44dbaff4b2533f1c1dbd1477","datavalue":{"value":"EXPTIME-complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068536$3CE0B7EB-012B-424D-BE2B-6D2547D3CD08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068536$58BE05B8-542C-4D2A-B2DA-3546A9687E17","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"488d048a8186245364a15937ead16119e53adf2e","datavalue":{"value":{"entity-type":"item","numeric-id":1176062,"id":"Q1176062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068536$C4BD891A-95E6-4EC9-9D26-D1FE32AAE128","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":"Q1068536$247A0063-AB98-450F-8A16-161AB5A83399","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":"Q1068536$922C1626-1DE3-463E-B1DE-1D7F37DC7B85","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":"Q1068536$6493F5B0-5AB1-487E-BCB1-ECB4FF8124E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27ae048a51566b9b30aabd668fe3c01dba8252d3","datavalue":{"value":{"entity-type":"item","numeric-id":1172386,"id":"Q1172386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068536$3CB82B0A-6A85-4859-BF82-C0ED658EA591","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":"Q1068536$BCF784E8-E03E-4A0E-8566-7C1A896892BF","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":"Q1068536$01554098-583F-4138-8E21-54028ABB194D","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":"Q1068536$7E05A263-BDB5-4189-B713-A08E819E6046","rank":"normal"}],"P1643":[{"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":"93fd572de071ca50a2eafb489418f1b30bbaa89b","datavalue":{"value":{"amount":"+0.80909353","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$709D4E49-99ED-4368-ABD2-1408FE64BFE1","rank":"normal"},{"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":"444bfbd860f8bb50329c241998e9c215da8100e1","datavalue":{"value":{"amount":"+0.80625874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$DAAE16C9-F237-4DDB-ACD4-A38F2FF489C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8ac3ea8bfb8ed4349d4bbffcfb10bd6ae96dc25","datavalue":{"value":{"entity-type":"item","numeric-id":1329733,"id":"Q1329733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a120ee8ea733170d85b45ed662f4e2786473812d","datavalue":{"value":{"amount":"+0.7944346","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$6C153900-06DD-486A-BFF3-D5AAFF23CC2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02d6e57a6c3df1da24f28131f52582bf05033667","datavalue":{"value":{"entity-type":"item","numeric-id":5311749,"id":"Q5311749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b13ff99b2fdbb09263b437cccbae5c4b42323ffe","datavalue":{"value":{"amount":"+0.78888625","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$942809B4-BD18-4623-AF7C-46F9E5A90AE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a06a8960d554c08fc9d564eb0a373a0cd788708c","datavalue":{"value":{"entity-type":"item","numeric-id":1107310,"id":"Q1107310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a8da07444263be00bdad66ee1b16fecb9ace92e","datavalue":{"value":{"amount":"+0.78880024","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$9DCE6934-55A3-4213-9C08-D25312019930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"197c18dbb41c267d50e8c6f162323d4c907a1cdc","datavalue":{"value":{"entity-type":"item","numeric-id":2906562,"id":"Q2906562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a399109dcc477bfd8c897b8108af4da467b3c0c","datavalue":{"value":{"amount":"+0.7861239","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$BE6C3683-3408-4024-8CA7-E65CE4D13209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cd942a080dc4a42fd8a4de00898378a6d9ff38b","datavalue":{"value":{"entity-type":"item","numeric-id":758202,"id":"Q758202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19559268d17e932991dd805567faf1bc8fdfc260","datavalue":{"value":{"amount":"+0.78572315","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$9B4B854D-1AD5-419E-92FD-79CD5E0F41EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4c4bc3351ee32a17134c83269b492b490b4afeb","datavalue":{"value":{"entity-type":"item","numeric-id":3483270,"id":"Q3483270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"366377fa749a34dfdf40cf231f3c6b249fb753d6","datavalue":{"value":{"amount":"+0.7631846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$F4C200C0-69CB-4864-9EF6-8541FDA748E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04edd5e1fd4cccaeb6a9b91b08c12edc584681c5","datavalue":{"value":{"entity-type":"item","numeric-id":1109766,"id":"Q1109766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fc0ac43000bc0a117f7bc274f4309c544f2e83e","datavalue":{"value":{"amount":"+0.76227087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$72952301-D2D0-4B5C-864C-8356A98EA7C2","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":"64f32b58053ce01d5e172af1ebd83f8626475d67","datavalue":{"value":{"amount":"+0.7606921","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1068536$E916DCA2-E72B-4F60-8E39-374C4E8A29CC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On one-one polynomial time equivalence relations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_one-one_polynomial_time_equivalence_relations"}}}}}