{"entities":{"Q1184732":{"pageid":1195481,"ns":120,"title":"Item:Q1184732","lastrevid":42308167,"modified":"2025-06-05T10:12:13Z","type":"item","id":"Q1184732","labels":{"en":{"language":"en","value":"Generic oracles, uniform machines, and codes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 34931"}},"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":"Q1184732$DBFEBA18-A3E1-4363-BD5A-4DA7B42527E6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee8fa92ebd87b086153d42e20adbff0a9c32fd7f","datavalue":{"value":{"text":"Generic oracles, uniform machines, and codes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1184732$58ED86EE-9F07-4784-9FBC-59AA0214B8D1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5eebb4615178f1ecfa1da0b769a33f331d11d7ba","datavalue":{"value":"0755.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184732$3936F1DF-A9FE-4837-AF6A-F56A52968AE7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9251cd298c19bfe9870967bc7617c7062ccdd140","datavalue":{"value":"10.1016/0890-5401(92)90055-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184732$13B8DF04-5AE4-4100-B7B3-A01FAA05FA21","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"024aa4aa4eee86712b059a7b98963fe87c1230e7","datavalue":{"value":{"entity-type":"item","numeric-id":1184731,"id":"Q1184731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$B56F77FC-54E2-462B-A2FE-177A4BEFCEC7","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":"Q1184732$C36AE09D-90BC-4291-9F3B-19880E678128","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1184732$1A9BC90A-2684-4D3F-818E-D02105A61FF6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4fc2c4db3939f4cc9ee69fecf6db63ef5610140d","datavalue":{"value":"This paper proves primarily the theorem that a nondeterministic oracle machine which for any oracle \\(X\\) accepts the tautologies relativized to \\(X\\) when running with oracle \\(X\\) does not run in polynomial time at any oracle. It is also shown that if \\(X\\) is \\(r\\)-generic, and no nondeterministic machine with oracle \\(X\\) accepts the \\(r\\)-query tautologies relativized to \\(X\\) in polynomial time, then \\(NP\\neq \\text{co}NP\\). In addition, some properties of circuits as a model of computation of the Boolean functions are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184732$952CC4E3-BA56-4F13-A7D5-9A47AA854705","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":"Q1184732$315E8CC5-D240-41B8-A3DA-1A946C2AAC36","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184732$778FB27F-38B4-405C-BC5F-C37773D3B3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184732$E45F3A75-5822-494C-A86D-491232F5093B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184732$E429C543-9CAA-4063-B8EE-C55416EBE026","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5c5b0872e7ebb7f112531a86f458e93ab22f3075","datavalue":{"value":"34931","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184732$115BA3CA-14DE-46F0-A105-F788DB4BFB15","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa882e30b561cc4f8cf15334fc95cf15e2661724","datavalue":{"value":"generic oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184732$3FCC4EC0-D404-4918-9CDD-54F357B136C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"911bc200d6c450de272a08fa5c19ef28484b1d94","datavalue":{"value":"tautologies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184732$076DB1E6-88CC-4B7C-8A1C-F764E7BD1725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c2773dc0449ebf96bb1747bc4f2b2f0a2faa889","datavalue":{"value":"circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184732$A25B4469-722A-4323-AD9B-6E9F55C98295","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":"Q1184732$E3040F62-71E4-4CFF-BC6E-3AF84A766486","rank":"normal"}],"P223":[{"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":"Q1184732$294A9E70-36E1-485B-8574-8DAC86674832","rank":"normal"},{"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":"Q1184732$8B0CF20A-4A4B-4EF5-B7CC-00DD5462940F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d88a1af1ba4970e30cf9005409b23a741c859fe","datavalue":{"value":{"entity-type":"item","numeric-id":5579041,"id":"Q5579041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$E2129664-851B-4774-8BEE-C7AF1F377392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"688e530530b2aa80b106b3a8c0a385dbe89600f0","datavalue":{"value":{"entity-type":"item","numeric-id":4068087,"id":"Q4068087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$932FEC81-C655-4C10-B0CF-FC53D0D472E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175c1c6339231426570e05a46d3193da46e70701","datavalue":{"value":{"entity-type":"item","numeric-id":4401926,"id":"Q4401926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$97028E89-7FEC-4D27-B813-530DAD3D9398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27e4af5b5876ff51622383a273f2390072da4ec7","datavalue":{"value":{"entity-type":"item","numeric-id":5338333,"id":"Q5338333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$9D90433E-2DBC-4202-9EE2-73515A770184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dff5354207b95fd4bf3a2fb6a6a282736abdbbfc","datavalue":{"value":{"entity-type":"item","numeric-id":5585410,"id":"Q5585410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$7E30396D-0823-456F-9F6F-4273272F947B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a181dd30afaafedddc5b141ee9b82f81ccc5fe9","datavalue":{"value":{"entity-type":"item","numeric-id":4185825,"id":"Q4185825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$32D28DF5-CD32-4695-B4B0-6993AF71E752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6de891d5a6744d6bc5da3b977613039967f9d10","datavalue":{"value":{"entity-type":"item","numeric-id":4191603,"id":"Q4191603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$B832E588-C38A-44BD-B59F-CB26C14A20C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5597a6addd334c0bee297bd66ef7c55229b04355","datavalue":{"value":{"entity-type":"item","numeric-id":3720579,"id":"Q3720579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184732$F3190AE6-8818-4A5F-B40B-54BC89A81A08","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":"Q1184732$6A1E096B-C883-48FA-B4E4-2CAAE5EA1136","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9650c01859cc53fd32ceb972b66649cda4571afc","datavalue":{"value":{"entity-type":"item","numeric-id":1119570,"id":"Q1119570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73f67cd8010213ea134ddaf528c877f0cc476222","datavalue":{"value":{"amount":"+0.8878067","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$B231F8A0-8F02-4ECF-AF09-458DD124D29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5bf62e7887061fc215f2c5110e8f620aa26d253","datavalue":{"value":{"entity-type":"item","numeric-id":3809784,"id":"Q3809784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73f67cd8010213ea134ddaf528c877f0cc476222","datavalue":{"value":{"amount":"+0.8878067","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$C4C909A5-C234-4A46-A507-F1C1CF9C9D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e5f7ef37c08cc7302972300e73c9c74f0e11da6","datavalue":{"value":{"entity-type":"item","numeric-id":4922664,"id":"Q4922664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb15e2929635fe5651ab7880fb3994183abee1a8","datavalue":{"value":{"amount":"+0.8799541","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$1BBC12C5-8F6C-486D-B437-165184160920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60f4e064537a348eccf57c8ea304f1b616a4753c","datavalue":{"value":{"entity-type":"item","numeric-id":1346911,"id":"Q1346911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79110518a9442bd761e57e1dee73277863c07eaf","datavalue":{"value":{"amount":"+0.87923396","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$7CE43CB4-B3F0-49C8-B001-EA7404749439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db8f956db4464ca8bdf772d10e61d4bca0e760e5","datavalue":{"value":{"entity-type":"item","numeric-id":1369098,"id":"Q1369098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1f64bc0c0477c2ed271f09cb50aae82717ac0cd","datavalue":{"value":{"amount":"+0.87289894","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$DE83523A-F109-4903-84A4-14F8646F47D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a594c2ac5fc5d32a46819f90d94382c54fc0e27","datavalue":{"value":{"entity-type":"item","numeric-id":1361886,"id":"Q1361886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4dc20149c515de760befcb6e4e5e1e427407d22c","datavalue":{"value":{"amount":"+0.8615055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$845C2D59-F768-4D28-953D-CAF91A6DF320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07a73e7315cd28e549ca912a6bee8817b2700b05","datavalue":{"value":{"entity-type":"item","numeric-id":1854543,"id":"Q1854543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26654f57ba94ff4c850535ffab6e3a3f72247109","datavalue":{"value":{"amount":"+0.85128194","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$DD2F500B-4EC8-4FC4-B691-FA39F7528B5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"775ed699fe70f242f850cec1757024928c26d38e","datavalue":{"value":{"entity-type":"item","numeric-id":2003343,"id":"Q2003343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc0a49c26834d76aed6b23339f585aa04f1eeea8","datavalue":{"value":{"amount":"+0.851177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$6ECAECBF-177A-40AB-B598-F4CC7B386B81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"544db40841c358c98abf68ee3c9e5e3dcca81354","datavalue":{"value":{"entity-type":"item","numeric-id":1351504,"id":"Q1351504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c5be8e34458ebf846e51256b5ff879128f26867","datavalue":{"value":{"amount":"+0.84670556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$F5532364-BA3C-4F3E-91C1-9E95E07E75DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4ad37700e8e303d5cb8d1f9bef2b9522640e0cd","datavalue":{"value":{"entity-type":"item","numeric-id":3340841,"id":"Q3340841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"881722c5f70737ea313938cccfc368e310c7ccfc","datavalue":{"value":{"amount":"+0.84540665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1184732$C0E5C567-709F-4D5E-BC87-15C802E6630B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1184732","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1184732"}}}}}