{"entities":{"Q1091817":{"pageid":1102569,"ns":120,"title":"Item:Q1091817","lastrevid":49081588,"modified":"2026-01-06T13:54:45Z","type":"item","id":"Q1091817","labels":{"en":{"language":"en","value":"On the notion of infinite pseudorandom sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4011935"}},"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":"Q1091817$83B8FE4A-4CC8-42C9-9822-39D16A3787A3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c362f1d15884ac44081939fa98ce379bd62df49f","datavalue":{"value":{"text":"On the notion of infinite pseudorandom sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1091817$6CE4840A-CA37-4449-B706-488D17817002","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"54d4a9f8a5c221e11f67ee48c48c7e4e6fcf0b6c","datavalue":{"value":"0623.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091817$780AC9C7-05E3-4879-9E1E-D53625C3EE6E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e957d42ff4d5dd8f9b7b7fd2e00f5cc6095bab61","datavalue":{"value":"10.1016/0304-3975(86)90081-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091817$A373DB3B-D722-4560-928A-73324A5D72CD","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":"Q1091817$51B38589-48AE-4A23-8649-DBDCE4684AF0","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":"Q1091817$C0C96F8B-561B-48F0-8678-A0557662034C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"85c8ec97c50831c0d88dea854abde39bb04ce447","datavalue":{"value":"The notion of infinite pseudorandom sequences with respect to polynomial time and polynomial space computability is studied. Three formal definitions of pseudorandom sequences are given, based on the polynomial versions of Martin-L\u00f6f tests, Kolmogorov complexity and von Mises's collectives. One of the main results is the study of the polynomial time and polynomial space versions of the Martin-L\u00f6f-Levin-Schnorr Theorem which states that an infinite sequence x is Martin-L\u00f6f random if and only if it has high monotonic Kolmogorov complexity. The polynomial space version of this theorem is proved, while the polynomial time version is left open with some evidence showing it could be a difficult problem. In order to develop this result, polynomial time/space-bounded Kolmogorov complexity of infinite sequences has also been studied. It is shown that there exists a double exponential time computable sequence which is pseudorandom with respect to polynomial time computability. Similarly to the randomness with respect to recursive computability, von Mises's definition of pseudorandomness is proved to be weaker than the other two definitions, with respect to both polynomial space and polynomial time computability.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091817$8AB7FD83-30DF-4242-9A61-A99A6FBA822C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091817$3EBC01ED-8ACA-4A24-868A-51ADE6468C43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e1f144a9ab7064f6f8c78503075f6cd455ea06f6","datavalue":{"value":"94A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091817$3438CCDC-D3FD-4B3A-88C1-5D6CEF7C814A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091817$99D6DEE1-CCFB-4566-9B16-06485EB40265","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"605838947fecd02a3ccbc0b2221369dc20ec5d40","datavalue":{"value":"4011935","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091817$DD636380-D4B3-4D7A-9C42-ED3F30C3A866","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bbd3a223a5b42157a3043622336c25140397692","datavalue":{"value":"infinite pseudorandom sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091817$B4AFDF6E-1B99-4806-A134-59FE39A6B437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091817$B4297E5A-22FA-46F5-A4CC-DBDE73A780E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"293fca54bd74430af61f2e21ff63e80d26cd97b2","datavalue":{"value":"Martin-L\u00f6f tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091817$84340367-C041-4B34-B321-BBF9259F1662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091817$43A7193E-2BF0-41FB-B949-7FE0B7D61A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f48f92ff0b29adb938dd74e93c94c7ffbb091bf4","datavalue":{"value":"polynomial space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091817$4FEA4317-6475-4DBD-8489-499AA94283A9","rank":"normal"}],"P16":[{"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":"Q1091817$DEEEC258-A71F-4DD5-845B-34B527E26F9D","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":"Q1091817$AE32D4A6-955F-4011-B03A-D1E4B6CC89B4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"995a2236cb7fca450538e41b1fabe539d20a33e3","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90081-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1091817$17C58AEA-53BE-4AA5-A117-A2DC4BBD247A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d74b28b1e4234c65b471715bc2a921337357ad5a","datavalue":{"value":"W2078472124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091817$C4AEACDD-F51D-47D8-83AF-03F26B6B17EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0596e5c599613b80ada37fb1d40e1b8f50bde8d","datavalue":{"value":{"entity-type":"item","numeric-id":5549809,"id":"Q5549809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$E466282D-A475-447F-A455-886ED8C3FED2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b729bbd6e61b662781ffb74f80a3e1dd1a8250d","datavalue":{"value":{"entity-type":"item","numeric-id":3738458,"id":"Q3738458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$50B092EC-70F2-4706-AA1F-1726D81E7413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a581f96e8cabd60b98280dbc93b840cb31eb7421","datavalue":{"value":{"entity-type":"item","numeric-id":3339289,"id":"Q3339289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$CFBC5CE4-4276-427A-92BC-152C9FC423BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"663c83b1b2405da7d703f0e171d190fef0cde5dd","datavalue":{"value":{"entity-type":"item","numeric-id":5541327,"id":"Q5541327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$909CAB69-DAFC-4AD8-89C9-7FBAF476484B","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":"Q1091817$9E33C2B2-67E7-4230-8F77-171F42EF8C42","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":"Q1091817$7F55E0BA-C1BD-4C48-B962-F527E42D704A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f42fd40f9916e6054a8b4a0674b07126a8cd4bb4","datavalue":{"value":{"entity-type":"item","numeric-id":4140388,"id":"Q4140388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$3B5DD689-B63B-4958-8C88-9F7B3DE0E2B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d29588960e1becc9ad6589918f35c0022c9c6b74","datavalue":{"value":{"entity-type":"item","numeric-id":5581618,"id":"Q5581618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$166F7B3E-AF3F-4269-B53A-518CED0BA48B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$F793E488-1D8E-4FFC-88FE-BCD6EC2E6DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2c5f4a456f9910b4c4f2a1d73e4561be8a5dbc2","datavalue":{"value":{"entity-type":"item","numeric-id":3214803,"id":"Q3214803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$45B15BB1-09B6-4A10-B9BD-0ADF0730EF4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59de21f0defbf2fa1496afd012acb0b2c70731ad","datavalue":{"value":{"entity-type":"item","numeric-id":4070738,"id":"Q4070738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$F87ACE59-2BC7-410A-AEE1-0B54DE255A7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66c928703c81779fae52967e0ccaf0c215e1df40","datavalue":{"value":{"entity-type":"item","numeric-id":5582801,"id":"Q5582801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$69E28E39-FDB0-495B-9267-2BC3513603E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cb06568540491b4e4dd3a7ff2ead4eda703f71e","datavalue":{"value":{"entity-type":"item","numeric-id":5656214,"id":"Q5656214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$E890DDDB-9A99-40A3-A823-667D05CB84B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76d0af4d4c3a77da444a77a20e1150664e1f0ced","datavalue":{"value":{"entity-type":"item","numeric-id":5594917,"id":"Q5594917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$795508B7-16F6-43F4-833B-79378AC9F0FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abaca2dcf79a5446bc203d3c2dec428bd26c5418","datavalue":{"value":{"entity-type":"item","numeric-id":5613696,"id":"Q5613696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$FEA35CE7-C3AF-4EE7-9999-809454D83399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d3feabf7738470c05cc9bc57fe6125054132512","datavalue":{"value":{"entity-type":"item","numeric-id":5684962,"id":"Q5684962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$9E2C1B19-4919-4AA3-B716-4A451C36E8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fed5fd3a0c1f3a22e44e4e1257dfbceb7db271a9","datavalue":{"value":{"entity-type":"item","numeric-id":5616138,"id":"Q5616138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$4D14023D-79CC-4F87-A074-E5DA3B7D5F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ee90301292f993937476af8a941fa54b3796566","datavalue":{"value":{"entity-type":"item","numeric-id":2264549,"id":"Q2264549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$777AB3E6-9A98-4752-9F7D-76DA6CAD7CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1ff743bf1ea4713fb4f26e1f381f14058a4f341","datavalue":{"value":{"entity-type":"item","numeric-id":4154541,"id":"Q4154541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$B391EEAC-8A29-41BE-96C9-F95BA361CEF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"647a872671d0d5878684e20e7bd23abcca08ee25","datavalue":{"value":{"entity-type":"item","numeric-id":3912481,"id":"Q3912481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$8092FB55-198C-4737-BB21-EDA8B4027548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55cfc0ff9590d7beb1ccb038cddeb12787b6740f","datavalue":{"value":{"entity-type":"item","numeric-id":5626617,"id":"Q5626617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091817$1A9B77DE-BAE5-48C5-84EB-65D886F830A9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84cc58930a784a1fc9ae9a5a36c47607f26ec14a","datavalue":{"value":{"entity-type":"item","numeric-id":3347291,"id":"Q3347291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70b0a114daf52db0b0129b2f64791e75b07809ef","datavalue":{"value":{"amount":"+0.866230309009552","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":"Q1091817$E6B19088-4C86-4D8C-A68B-7E83CC281C72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a933a9bfcc262f427f182369a3cfd4085b2d1b81","datavalue":{"value":{"entity-type":"item","numeric-id":3780469,"id":"Q3780469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e4cab2594b4b971957316ea55f9e6d79ab56306","datavalue":{"value":{"amount":"+0.8408454060554504","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":"Q1091817$035A9552-D148-4EF6-9825-BD53B44B25A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc2c4cfcc7447e808f078a72e496d2d99b8d0dd2","datavalue":{"value":{"entity-type":"item","numeric-id":3350762,"id":"Q3350762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db99307940491adf7459fb9dc6ee62717a031c93","datavalue":{"value":{"amount":"+0.8334490060806274","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":"Q1091817$92CC2A2E-8C82-477D-800C-B37EBEA32D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dca75ea7427bf8d6045eac897ce0a4d85a66c528","datavalue":{"value":{"entity-type":"item","numeric-id":3358118,"id":"Q3358118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95dcbf6fa3a7bc1b836334019bbbd4178ba4fc64","datavalue":{"value":{"amount":"+0.8228199481964111","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":"Q1091817$67D7F78F-36C2-4AA7-9A91-4F8C5755A8B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb3462951a92d8c596115fea4560edd7be2da816","datavalue":{"value":{"entity-type":"item","numeric-id":5288890,"id":"Q5288890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb784befdddd33be61812b130f5fe058c11fc356","datavalue":{"value":{"amount":"+0.8194999098777771","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":"Q1091817$75792F0C-EDB8-4E56-B07A-CDF1652A23E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1091817","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1091817"}}}}}