{"entities":{"Q2364655":{"pageid":2375398,"ns":120,"title":"Item:Q2364655","lastrevid":52864667,"modified":"2026-01-23T16:23:47Z","type":"item","id":"Q2364655","labels":{"en":{"language":"en","value":"On polynomial-time relation reducibility"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6751303"}},"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":"Q2364655$9A1DA0B6-9F42-4ED6-B873-D0ABEEC73C7F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"634b79e25971e9bc9317244768deb09f1c3142e5","datavalue":{"value":{"text":"On polynomial-time relation reducibility","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2364655$0F528867-A148-492F-87A8-04B2DE6A4078","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8759c9b9d974d57c4292b65de4a7afa519116302","datavalue":{"value":"1425.03015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364655$D9E9BEB5-A0D4-4CF9-ACB9-27A209FCCD72","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f1bdfcccc38f1ad1f06de373169f26d3c30cbb69","datavalue":{"value":"10.1215/00294527-3867118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364655$9718A32E-5B3C-4B37-9211-0291CC53992E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d2b264e376d370e18d6d207d6d992ada669ebf5a","datavalue":{"value":{"entity-type":"item","numeric-id":195360,"id":"Q195360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364655$085342EA-6311-4EBC-811D-B268F7C8501A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"13f8646b5994806ff25060ea3fee1b4902ddf576","datavalue":{"value":{"entity-type":"item","numeric-id":2364654,"id":"Q2364654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364655$374A38CB-1423-4C99-A17F-8E7F9AC86DF2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364655$AA686C37-542D-49D5-AD78-285179B14B60","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"36ae9f0663dd67e81623b5f2360b90198adfccf0","datavalue":{"value":{"time":"+2017-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2364655$D7B49EC6-E83C-4537-9413-7C7204D7B28C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"da35ca02dedd6b8951498fa85d540dc9c89d2e1e","datavalue":{"value":"https://semanticscholar.org/paper/91b4f8d5270b0ec608fef3bb09277c87650694e8","type":"string"},"datatype":"url"},"type":"statement","id":"Q2364655$49A886A3-3B86-4E6C-85F5-1E13BC1C4D81","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d65ef59a5578eba86f020f3c8211f4b2b5dd44c6","datavalue":{"value":"Equivalence problems (such as graph isomorphism, Boolean formula equivalence, etc.) can be viewed as equivalence relations \\(R \\subseteq \\Sigma^* \\times \\Sigma^*\\) for some finite alphabet \\(\\Sigma\\). Let \\(R,S \\subseteq \\Sigma^* \\times \\Sigma^*\\) be equivalence relations. Then \\(R\\) is said to be \\textit{polynomial-time relation reducible} to \\(S\\) (written \\(R \\leq_R S\\)) if there is a function \\(f: \\Sigma^* \\to \\Sigma^*\\) computable in polynomial time such that \\((x,y)\\) in \\(\\Sigma^* \\times \\Sigma^*\\) is in \\(R\\) if and only if \\((f(x),f(y))\\) is in \\(S\\). This requirement is stronger than in the definition of standard polynomial-time reducibility, where the reduction function depends on pairs \\((x,y)\\) in \\(\\Sigma^* \\times \\Sigma^*\\); for relation reducibility, the reduction function \\(f\\) depends just on the projections \\(x,y \\in \\Sigma^*\\). Relation reducibility was introduced under the name \\textit{kernel reducibility} in [\\textit{L. Fortnow} and \\textit{J. A. Grochow}, Inf. Comput. 209, No. 4, 748--763 (2011; Zbl 1238.68061)] and studied under the name \\textit{strong equivalence reducibility} in [\\textit{S. Buss} et al., J. Symb. Log. 76, No. 4, 1381--1402 (2011; Zbl 1248.03060)].  The authors prove several fundamental properties of relation reducibility, mostly demonstrating structural richness of \\(\\leq_R\\) on the class of computable equivalence relations. An infinite ascending chain and an infinite antichain with respect to \\(\\leq_R\\) are constructed. The main result proved in the article states that the partial order of polynomially computable sets of natural numbers can be embedded into the quasi-order \\(\\leq_R\\). More precisely, let \\(\\mathrm{id} \\subseteq \\Sigma^* \\times \\Sigma^*\\) denote the identity relation and \\(\\mathrm{E}_{\\lambda} \\subseteq \\Sigma^* \\times \\Sigma^*\\) be a relation such that \\((x,y)\\) is in \\(\\mathrm{E}_{\\lambda}\\) if and only if \\(|x| = |y|\\). Let us denote the set of all polynomially computable sets of natural numbers by \\(P_{\\mathbb N}\\). Then there is a mapping \\(\\varphi: P_{\\mathbb N} \\to 2^{\\Sigma^* \\times \\Sigma^*}\\) such that \\(\\varphi(X)\\) is an equivalence relation satisfying \\(\\mathrm{E}_{\\lambda} \\leq_R \\varphi(X) \\leq_R \\mathrm{id}\\) for each \\(X\\) in \\(P_{\\mathbb N}\\), and \\(X \\subseteq Y \\iff \\varphi(X) \\leq_R \\varphi(Y)\\) for each \\(X\\), \\(Y\\) in \\(P_{\\mathbb N}\\). Properties of relation reducibility on special classes of finitary equivalence relations are studied as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364655$5B26317C-3E4D-4026-BD7F-D4754581DA66","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f820636d9adc44c2af172b05e36a9c0ce0f020b5","datavalue":{"value":{"entity-type":"item","numeric-id":782589,"id":"Q782589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2364655$62BD8A64-4CF8-496E-82E5-881701DC5AA1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364655$2C78C418-952C-4376-8389-6235E3E0F11A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364655$2BDC6035-5664-4ABC-8703-12DE92EED433","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"01b238c0d1ee6d431058074d74826244c585cba5","datavalue":{"value":"6751303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364655$D3923869-EF8B-42D3-AE49-16FE28C90A9C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bb367fd2f5f2c5c33c9df788ec7eedc752293d8","datavalue":{"value":"relation reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364655$B690B78B-7652-405A-94C8-E5A4CE706804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60d27bfd180426c7f7a6d7a0ec099a7b8c7221ec","datavalue":{"value":"kernel reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364655$D8481B6B-2C13-403D-B234-1362668B28FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe99fb619138f140e4259606fe0fd2a71a1f80","datavalue":{"value":"strong equivalence reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364655$5E50111D-67DF-4F61-9FE2-9BF4E733DB33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ca57d225358d55c161d2fd9284b1f4649a91fc4","datavalue":{"value":"polynomial-time reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364655$1804ED59-9DAC-45DB-BAC1-232B4280B216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bf0a69ff86a1d56569a9610bc144fdfce86ab79","datavalue":{"value":"equivalence problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2364655$7233FA51-DCC0-4037-8536-620611F28B87","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":"Q2364655$3E66B4DE-0221-4AF0-8ABE-055226957CA9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f0a777f2aa56d136e517f1eacdd28a85f040af18","datavalue":{"value":"W2186033963","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2364655$B1A8CEC4-89A5-4324-9D6E-DC7BE95C4A27","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61bd4c3c57ca648e3eb56fb0e97310bac8e7107c","datavalue":{"value":{"entity-type":"item","numeric-id":2976331,"id":"Q2976331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e109add76dffee638c26ecc33dc9ae2caf35a2b7","datavalue":{"value":{"amount":"+0.8143096566200256","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":"Q2364655$A42D105B-9066-4F6E-991A-38E1952B8F94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b3dfbdaf48ad859cfd2aa0184105a4901a0ed18","datavalue":{"value":{"entity-type":"item","numeric-id":676314,"id":"Q676314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40194261c4884dcf36c9fa713dde6937ffb0cf52","datavalue":{"value":{"amount":"+0.801302433013916","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":"Q2364655$4A0257B0-3B67-499C-B703-CD5EE7112B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b6a749daca74274607b140e6956670c7a602c85","datavalue":{"value":{"entity-type":"item","numeric-id":4904456,"id":"Q4904456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51a027352a1d6dcbb96d5be588a003a513941267","datavalue":{"value":{"amount":"+0.7985986471176147","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":"Q2364655$76670156-79B8-47A5-8BBD-879F6CF1D2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39d4aefadcc5e564391cd2be93fa4fb2beb946b8","datavalue":{"value":{"entity-type":"item","numeric-id":2915014,"id":"Q2915014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69bf2d3acfd1335311bb6ba66242f3a43b434c00","datavalue":{"value":{"amount":"+0.796516478061676","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":"Q2364655$DCF916BD-880D-43BD-BC62-C623473EE192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44b06694f20e348410c65be8682957667fc2fe45","datavalue":{"value":{"entity-type":"item","numeric-id":2933680,"id":"Q2933680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e6dddccb36a27a09cea987df7b026b8605dfe19","datavalue":{"value":{"amount":"+0.7956598997116089","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":"Q2364655$5296E165-152A-44D0-B3A2-744532DFC919","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2364655","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2364655"}}}}}