{"entities":{"Q2366567":{"pageid":2377310,"ns":120,"title":"Item:Q2366567","lastrevid":46345578,"modified":"2025-12-24T14:57:15Z","type":"item","id":"Q2366567","labels":{"en":{"language":"en","value":"Using self-reducibilities to characterize polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 227136"}},"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":"Q2366567$051459B2-F511-4B5E-B7AA-99A61A38C45F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6d326f7480a7f49233d974f0b2eed6b7313f9034","datavalue":{"value":{"text":"Using self-reducibilities to characterize polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366567$8C91D276-ED58-4D41-9D4B-A6368D2F6CB1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"64df6c6a7981089b1cde55e0360ae961ba9d410c","datavalue":{"value":"0776.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366567$7DB8972E-352E-4B60-B5BA-047FD00D0435","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366567$BB2748A8-A43C-4E5F-9306-641E0062A0F0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366567$70732828-8569-4139-847C-EB274D02438D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca925aef735ee73d86c6a323015bc1282d85f7d8","datavalue":{"value":{"time":"+1993-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366567$90BC91C3-C745-4247-89E6-6A2AE0AEA0E7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d87b375ca846f9233e63061dad5845b356a399fa","datavalue":{"value":"http://digital.library.wisc.edu/1793/58934","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366567$133F88ED-CCA5-43C4-BDF8-B448D1CB8304","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"beb3e6c4c1d3b04da433f69edd701e0a679c2937","datavalue":{"value":"The effect of a set having a self-reducibility structure is studied. Three variations on the notion of Turing self-reducibility are studied: near-testability, word-decreasing self-reducibility, and \\(p\\)- cheatability. The complexity class of polynomial-time computable sets is characterized in several non-trivial ways using the above notions. In the concluding section several research questions building upon this work are posed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366567$B88BAEAD-9A09-4EDB-8070-41584022B06B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366567$A21B803C-1998-4BA8-A6A9-982BA285940F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e3d0623e923ea68cd23cc82412c607a445779bb","datavalue":{"value":"227136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366567$5CC6D34A-5B0A-4D5B-87BF-80D1F939B872","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bf39ff67c734ccef72308ae15736ee44ba84c0c","datavalue":{"value":"self-reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366567$ECBC722B-F354-48D1-88CC-FA3252F19C8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5201de7420bfe67765128c0d64b6c593baa1e92","datavalue":{"value":"near-testability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366567$87822182-84DA-47E8-BBB0-03BFCCD5E7CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d385764d86ad14a441f1f243bb45a60bb3c2396","datavalue":{"value":"\\(p\\)-cheatability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366567$2F19CADA-568A-4C6F-B0E0-F73E536A6345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9eacef8b5f25c3a09dcca27d202c1325863372bb","datavalue":{"value":"polynomial-time computable sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366567$F9F97EB5-DB1E-40D4-B038-71C9B8D1FB68","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":"Q2366567$1E268CDE-B294-44BE-8AF1-6EA165B76CB1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b643edfc6066dc88bcf0c325e7faa34ccc1966a9","datavalue":{"value":"W2034041719","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366567$3EB90155-7757-45D1-80AA-FD22853879DD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3f0fa7f43de5543af856375525a789c223a0316e","datavalue":{"value":"10.1006/INCO.1993.1035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366567$A3D45BE1-3DEC-4AED-874B-4A0A0B2BCBC8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a9e2014cc3ff26f697a58cc7ed0969a709af926","datavalue":{"value":{"entity-type":"item","numeric-id":672402,"id":"Q672402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfaa89ce607cca6c71b5dfcf3681ff84eea644d4","datavalue":{"value":{"amount":"+0.8074526786804199","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":"Q2366567$FB94A4E5-1C5E-483C-A79E-7AF4690EFF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f226b054ab1d6c2099db4b18b45800ffbca00a8","datavalue":{"value":{"entity-type":"item","numeric-id":3489449,"id":"Q3489449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b364570de94b8a250576d45a0acd4547ab7e7555","datavalue":{"value":{"amount":"+0.8057147860527039","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":"Q2366567$B1331995-F201-45EE-BF08-588DF447AEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b955f16ff5117ba1f761205d1e05627019c3949b","datavalue":{"value":{"entity-type":"item","numeric-id":3820010,"id":"Q3820010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaf392d36616098b9791927a417e2588983d3d74","datavalue":{"value":{"amount":"+0.8043609261512756","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":"Q2366567$17AB2E97-B4E2-4558-A8BE-4E2DF7E5D539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa7cd9092d8602af88830f71145ee81972fade89","datavalue":{"value":{"entity-type":"item","numeric-id":4206394,"id":"Q4206394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"337ad337fd71b92c19c1f85385282a8d652b9a7a","datavalue":{"value":{"amount":"+0.7993176579475403","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":"Q2366567$892B111C-25E9-4128-9D9E-D0C8264C242E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2366567","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2366567"}}}}}