{"entities":{"Q1096587":{"pageid":1107339,"ns":120,"title":"Item:Q1096587","lastrevid":77752580,"modified":"2026-05-06T09:58:52Z","type":"item","id":"Q1096587","labels":{"en":{"language":"en","value":"One-way functions and circuit complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4031573"}},"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":"Q1096587$683F42DF-43E2-4769-A5FF-3FD838EDBCE3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a99ef7f7b1f3e7254d9e0a304715bc7b640ff3c9","datavalue":{"value":{"text":"One-way functions and circuit complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1096587$91B84096-A620-4472-BFC2-BCACCD57880C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c29bc30c8490614dcdac829f429b16868e6dc84c","datavalue":{"value":"0633.94015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096587$2D50DD0D-7843-459D-8045-E805DCD9674C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d3303d72092b49f9bd4038d26c088f174d3e97db","datavalue":{"value":"10.1016/0890-5401(87)90022-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096587$616BF2B3-591A-42C7-BADC-3662822FA91C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5bf5a07a70c009b9407b5ef2db9026ca798e998f","datavalue":{"value":{"entity-type":"item","numeric-id":290254,"id":"Q290254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$1EDA9993-E70A-4B5D-A2FC-4E3F8034D598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e6283423bae8ab43988467847749f70d404423f0","datavalue":{"value":{"entity-type":"item","numeric-id":176453,"id":"Q176453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$1CF9ADE6-5536-432E-B553-7E27EF42E202","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":"Q1096587$84621C73-82A3-4D51-8284-3FC81C08C5E0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1096587$430A4ADD-EE13-49D2-8EA7-423DF63E70C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"939aed7c527b225ab4166831ab5d225f08b07414","datavalue":{"value":"Several distinct definitions of one-way functions have been proposed based on Turing machine complexity. This paper defines one-wayness based on circuit complexity: A family of finite functions is one-way iff it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. It is shown that 1. There exists a one-way family of functions iff the satisfiability problem SAT does not have polynomial-size circuits; 2. There exists a one-way family of one-to-one functions iff \\(PSIZE\\neq UPSIZE;\\) 3. There exists a one-way family of one- to-one and onto functions iff \\(PSIZE\\neq UPSIZE\\cap co-UPSIZE.\\) This paper then deals with similar questions concerning the relative complexity of checking versus evaluating and gives three complexity results for the checking versus evaluating problem parallel to the above results. Finally, this paper gives two examples of provably one-way permutations for constant depth circuits.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096587$D5E214AC-73B0-4EDC-A40D-E010FB7E508B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096587$A9EF9A7D-FD39-40AA-A579-E5529B4CC1D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096587$1B73D86B-D381-4547-B499-EB40CEC337AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096587$2C5DEA34-EC13-47D8-BEA7-19CBE391ED93","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c3a034491aee02d23b611e4dec8bea9f1e03a12f","datavalue":{"value":"4031573","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096587$1B1F9B64-6951-457D-AD2B-FD93C2B2EE00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a2b24f6056a67bc35da06909c9272de4feab241","datavalue":{"value":"one-way functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096587$2E135448-19AF-4AD1-8E6A-F36BD19166C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8496456291708c9df73cf7700c6d79f3c283501f","datavalue":{"value":"Turing machine complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096587$3926D07A-E23A-4654-B265-4925F07D8A51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34d0ff19151e759b74107d4104a16d851f0f91ce","datavalue":{"value":"one-wayness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096587$5769636B-D333-4CFB-ACF5-275AEA25BBB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096587$C9CBABCC-73C9-4FFE-8E98-34709C339C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"350412f42c610bfa4e85a0407a17babab4f3eefd","datavalue":{"value":"finite functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096587$0A15FF29-1798-4BD8-A909-E194C949FCC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a428018fcb62c231dc4b5243845a1705be4384e3","datavalue":{"value":"polynomial-size circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096587$F85E1291-37B5-4A67-BE5C-9ABA5D927554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0b4d6e6089943a261128dec792d30fd4cdc9763","datavalue":{"value":"satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1096587$8387D360-8725-40DC-95AE-A73BD388E533","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":"Q1096587$C9B15864-9D39-4D85-829C-D5D0B8D86679","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":"Q1096587$C7FA8B8D-359F-465D-A616-A20A40BA7ADC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b0d46d9906e8c2f69c7b69947a9276fa425b20bd","datavalue":{"value":"https://doi.org/10.1016/0890-5401(87)90022-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1096587$6EA16AFA-50BB-4ADD-A5E7-7F7346F68C26","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"664dc6f58293e500df890fc96773df886c6b2b05","datavalue":{"value":"W2060260518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1096587$4807ABA7-3D98-4C24-BBF1-E2A54B5CCD45","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$B90C0E71-643F-4D0A-9485-69D7CE63B598","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":"Q1096587$0E65823F-EE8B-40DC-A3EB-C0729CE552A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"575d0ef788c7cb963dec7aaa9856e0f7595da4fc","datavalue":{"value":{"entity-type":"item","numeric-id":3689089,"id":"Q3689089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$D417837B-EAA2-4FE2-B884-E199F5A9E0F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa57810f0528ce2438cd0f484c242c53bb4e54","datavalue":{"value":{"entity-type":"item","numeric-id":3325043,"id":"Q3325043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$660F040F-BFFC-480A-8007-87BA8E5E62D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$16539A24-007F-465D-BF41-074E05A4C46B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$5CE2CEAB-516C-4974-AD81-FF8C79F3659D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c4e0f1e7245c689fd4b9eaebca2d2d06145423","datavalue":{"value":{"entity-type":"item","numeric-id":1108786,"id":"Q1108786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$CF772DA9-81A0-49B4-B44E-A83D409E6093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df9b440a7e27b4753042460b886584e943bebd26","datavalue":{"value":{"entity-type":"item","numeric-id":3957950,"id":"Q3957950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$EDA27B9D-32DC-484B-907D-5A8ED2B601A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18b1eff86e275eabe1de48fbbe338962260427bd","datavalue":{"value":{"entity-type":"item","numeric-id":1100894,"id":"Q1100894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$38FEE682-323A-4BB2-8313-E6FE9D600B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f3f8c402957e2c95095405c7dd38cb2d24866a8","datavalue":{"value":{"entity-type":"item","numeric-id":1149766,"id":"Q1149766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$560249E2-1A91-48B5-B1E0-E3062759D880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c551822e86c0407675a9f9f7fcb1ddd9dd22246b","datavalue":{"value":{"entity-type":"item","numeric-id":3726006,"id":"Q3726006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$43A6DB1F-3603-4C30-BE41-F6FB05CC6E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4ab13142076117cc14856c9cfe9c081eaaa2f9d","datavalue":{"value":{"entity-type":"item","numeric-id":4172915,"id":"Q4172915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$08D07451-8808-462D-95AC-E1F3E1FF1C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3fdeac57e6ae30181fb2db5f7f4e10e134e5670","datavalue":{"value":{"entity-type":"item","numeric-id":1232181,"id":"Q1232181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1096587$4B1E505E-9C4A-40FA-BDF4-6801B8799AE4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"396254899a5d3a4327dec0ec31ddbac85dde6a8f","datavalue":{"value":{"entity-type":"item","numeric-id":3753481,"id":"Q3753481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02aab1dbc478343bd012c7b803b04932e5e52803","datavalue":{"value":{"amount":"+0.9733011722564696","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":"Q1096587$7F51EA07-7558-4A83-A4DC-E8DF6DAB57B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68666d51c81a7dd58379ed206ce2b0b20f237ecc","datavalue":{"value":{"entity-type":"item","numeric-id":4205082,"id":"Q4205082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc2bd2e794435fd73b173fc10e328a435828bb33","datavalue":{"value":{"amount":"+0.8919633030891418","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":"Q1096587$37426D4E-2B96-4D86-8EBA-65F274A22811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7ec548350db475d223238485e7ad51859fd4198","datavalue":{"value":{"entity-type":"item","numeric-id":4009812,"id":"Q4009812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6c6cbe262c4c8d994a1fbacb15f2717f708d594","datavalue":{"value":{"amount":"+0.8750393986701965","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":"Q1096587$EAA7A81B-34B0-4AC7-B42A-D024DB6D7CCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b3d0ed53a887a3d47030a5855fc446321986dc5","datavalue":{"value":{"entity-type":"item","numeric-id":3833992,"id":"Q3833992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e508a63d3ce0a6402048e99b65a584f7b021ada","datavalue":{"value":{"amount":"+0.8694169521331787","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":"Q1096587$CA420ECD-10E4-45D1-AEB0-A2F68DF04FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6877e34fd18cb00bf833077239668e2a39f53c7","datavalue":{"value":{"entity-type":"item","numeric-id":3224957,"id":"Q3224957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efa29a325ffa98c79627c01344638fb5b2897569","datavalue":{"value":{"amount":"+0.8307462930679321","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":"Q1096587$694E2302-2EE9-4559-BC14-CE29C4579A81","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"One-way functions and circuit complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/One-way_functions_and_circuit_complexity"}}}}}