{"entities":{"Q1097694":{"pageid":1108446,"ns":120,"title":"Item:Q1097694","lastrevid":69635148,"modified":"2026-04-13T08:21:22Z","type":"item","id":"Q1097694","labels":{"en":{"language":"en","value":"On one-way functions and polynomial-time isomorphisms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4035139"}},"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":"Q1097694$94BB4739-7661-414D-B332-81067FE1AF5B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d2b5467725b68b1c03286a6b60a1719a646de592","datavalue":{"value":{"text":"On one-way functions and polynomial-time isomorphisms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097694$AF18119A-7236-437D-8B65-86ADF2DF4FA3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c74442693b08a4042b2764fd3b3382d487245a34","datavalue":{"value":"0635.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097694$B3750851-B7A7-4B1E-8550-A5BC2E01A559","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"229694956c7055643b4e5c56a7942eff6c2a215f","datavalue":{"value":"10.1016/0304-3975(86)90152-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097694$9D893095-A9C0-483A-AF0A-1AECFDE19FA9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ab62c892d378963e4ddd263f29ad88202d8991f","datavalue":{"value":{"entity-type":"item","numeric-id":1055404,"id":"Q1055404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097694$AD8DF8DA-6FE0-48C4-86EA-764C0945434E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d176dcf8014bfec2c4899579ee7ce9e18294338","datavalue":{"value":{"entity-type":"item","numeric-id":166203,"id":"Q166203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097694$0111FD95-4C92-4F8D-8E77-FA9BFBFD9C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"13bc86079a0769c5ab1c6f28dc4e52a39f4a573a","datavalue":{"value":{"entity-type":"item","numeric-id":1295380,"id":"Q1295380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097694$C038988E-1282-4025-A37D-52EBB68F1688","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":"Q1097694$A3086C88-6CAC-408D-B108-10D585014228","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1097694$CA838A6A-F05F-47CC-83F2-01375A239518","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"71508b3e0eac7a91b5d595c866f84c09f004dcbd","datavalue":{"value":"Two sets A and B are polynomial-time isomorphic if there exists a polynomial-time computable, polynomial-time invertible, one-to-one correspondence f between the domains of the two problems such that \\(x\\in A\\) iff f(x)\\(\\in B\\) for all instances x. On the basis of the observation that all natural NP-complete sets are polynomial-time isomorphic, \\textit{L. Berman} and \\textit{J. Hartmanis} [SIAM J. Comput. 6, 305-322 (1977; Zbl 0356.68059)] conjectured that indeed all NP-complete sets are polynomial- time isomorphic. \\textit{D. Joseph} and \\textit{P. Young} [Theor. Comput. Sci. 39, 225-237 (1985; Zbl 0597.68042)] noticed that k-creative sets, a new class of NP-complete sets, do not seem to be polyomial-time isomorphic to natural NP-complete sets unless one-way functions do not exist. They conjectured that if one-way functions do not exist then not all NP- complete sets are polynomial-time isomorphic.    The existence of one-way functions is, in this paper, related to the question of whether the EXP-complete sets are all polynomial-time isomorphic. It is known that the EXP-complete sets are equivalent under one-one, length-increasing polynomial-time reductions. Using the polynomial version of the Cantor-Schroeder-Bernstein construction, as described in Berman and Hartmanis, it follows that if one-way functions do not exist, then the EXP-complete sets are all polynomial-time isomorphic. It is proved in this paper that the existence of one-way functions is sufficient to distinguish, in the class EXP, between polynomial-time isomorphism and equivalence under one-one, length- increasing reductions. Furthermore, such sets can be made to be truth- table complete for EXP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097694$D1230E47-CA1B-4640-A889-03C1687F7AE3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097694$A75B449B-9BAE-4240-B8EB-287715FBA135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097694$5FC9D8C0-3FB5-418B-8A99-76505C386567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097694$1E88D2D5-E2D2-4F76-85B9-4E3CBE976365","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"399446b1947678d09ac6f979c5a36b21f9bad325","datavalue":{"value":"4035139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097694$6165D303-85B0-4226-9340-E5510380ADD2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a2b24f6056a67bc35da06909c9272de4feab241","datavalue":{"value":"one-way functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097694$55F260CF-DBDF-4604-A51A-55384496205A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18b896e4875df610358fccf59713481feead9685","datavalue":{"value":"NP-complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097694$53CCDE8F-65B6-4F1C-9BB6-BBB682202F3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52d1e352e938f3b1bfd99c16386ae1c32707bc64","datavalue":{"value":"EXP-complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097694$F9ED62F1-04EF-4204-877D-2F1C8BCAC3EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2eee6c553bfe2d649080f7afc9e542ad509166a3","datavalue":{"value":"polynomial-time isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097694$004F1A50-CD14-400D-9C7C-8755DA551376","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":"Q1097694$E4CC8BBD-7E20-4BAC-80A1-263B3B089F4F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d28e1828d499ca8539d67cd0b3000748c7e5f29a","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90152-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097694$B5F8EFAD-4A94-44AE-8ECB-07A4DCC6308E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"14b1b6635f8a284b32728240b511f96fabaf3094","datavalue":{"value":"W2078503376","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097694$22FD162B-8F5C-4528-8703-BDE3C7D67989","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":"Q1097694$C5779FAC-6F3A-4049-9CC2-4F2F541BF6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cc337081946f14db7d7419525432c213b488aaa","datavalue":{"value":{"entity-type":"item","numeric-id":5413416,"id":"Q5413416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097694$896588FA-3D8E-48DC-B559-2DEDDCA436C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb51cb599580481aadcbb3a7e805e65dbcbf5ce5","datavalue":{"value":{"entity-type":"item","numeric-id":1079364,"id":"Q1079364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097694$4635B63F-ECC3-45CD-AB3F-F95856B339B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11fc8f5bb5704d3224b97e588e8093982d5aaed5","datavalue":{"value":{"entity-type":"item","numeric-id":1064780,"id":"Q1064780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097694$E6E138FF-F8A6-4509-8A06-369D5DBE4393","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":"Q1097694$4346EF02-647C-4A8A-A19E-11D638817206","rank":"normal"}],"P1643":[{"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":"12905e30c7022752e5bfe8959b701e3d0025cb91","datavalue":{"value":{"amount":"+0.8901217579841614","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":"Q1097694$1C74DA77-AF2A-4C0D-8EE5-A4CA10DD905E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27792ad07f2d0b0f291a57fdafea46136b642460","datavalue":{"value":{"entity-type":"item","numeric-id":4369869,"id":"Q4369869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24a6101da4e5c4b813869cfde687d177d0b12704","datavalue":{"value":{"amount":"+0.8866757750511169","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":"Q1097694$6C7454F7-CB1D-4B06-AD63-4185297B0BE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cb4032f6e71da85d9e5b561d8dafe0e35cd9f1d","datavalue":{"value":{"entity-type":"item","numeric-id":2639055,"id":"Q2639055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe22340133c7bc3054565eb818fcbab8349db30c","datavalue":{"value":{"amount":"+0.8792210817337036","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":"Q1097694$1B8EB9D1-D2C6-4FB5-8EFF-A4688408720A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5199f46355adb4ed2c92a180bb5091e56ba0058f","datavalue":{"value":{"entity-type":"item","numeric-id":4256648,"id":"Q4256648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fadccee62f227664df55f15db74689d6ec5c4241","datavalue":{"value":{"amount":"+0.8693262338638306","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":"Q1097694$12688497-1A57-445F-BDE3-FA0C17268693","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":"ea8d40616ff5b51b6ecefafff6727ad11cad6daa","datavalue":{"value":{"amount":"+0.8686764240264893","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":"Q1097694$D4D5EFBA-4CBF-4377-8920-4FB6DD1C6491","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On one-way functions and polynomial-time isomorphisms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_one-way_functions_and_polynomial-time_isomorphisms"}}}}}