{"entities":{"Q666698":{"pageid":668547,"ns":120,"title":"Item:Q666698","lastrevid":63502119,"modified":"2026-04-11T13:36:05Z","type":"item","id":"Q666698","labels":{"en":{"language":"en","value":"Inverse monoids associated with the complexity class NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7034513"}},"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":"Q666698$2A2BEC77-554D-4874-AC5F-B13BB6FD111D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"40d12d182d21f6196be10e1349353ac2f0604c0b","datavalue":{"value":{"text":"Inverse monoids associated with the complexity class NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q666698$0FB53A41-FC67-4D37-B2CF-E0D1728599E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9d801d498ca0bb8a19eaf49670a09cf86fb77d06","datavalue":{"value":"1419.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666698$B06262EE-E6C2-455E-B6CE-1FFC233918D8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"28dbf90a09492d81530507fd711b9336815e58a3","datavalue":{"value":{"entity-type":"item","numeric-id":172569,"id":"Q172569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$376D5E86-9C41-466C-A33C-5C9827D35E0B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"40f1e50024e8819cb0b85124b28367c18d16eca6","datavalue":{"value":{"time":"+2019-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q666698$E3A3F453-7172-414B-A7FE-42677D4F0802","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6de13509123f4fc9cbc2f959f8be8284cf3d96b5","datavalue":{"value":"https://arxiv.org/abs/1703.02519","type":"string"},"datatype":"url"},"type":"statement","id":"Q666698$337566AC-9EAD-4966-8604-2BCB3C0F13F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a85f45255a3fad101198feab7129a92975230f7","datavalue":{"value":"The basic unsolved complexity-theoretic problems \\(\\mathrm{P}\\neq\\mathrm{NP?}\\) and existence of one-way functions are tackled considering algebraic properties of partial polynomially balanced functions acting on finite strings over the alphabet \\(A = \\{ 0,1\\} \\) computable by a deterministic polynomial-time Turing machine; a function \\(f:{A^*} \\to {A^*}\\) is polynomially balanced iff there exists a polynomial \\(p\\) such that \\(|f(x)| \\le p(|x|)\\), \\(|x| \\le |p(x)|\\). It is known, that \\(\\mathrm{P}\\neq \\mathrm{NP}\\) iff there exists a polynomially balanced function computable in polynomial time by a deterministic Turing machine which does not have an inverse that is computable in polynomial time, and functions that are polynomial-time computable and polynomially balanced, but have no inverse of that type, are one-way functions. Here, the author studies properties of several algebras of such functions: the monoid fP of polynomially balanced polynomial-time computable functions, the reverse monoid invfP of injective functions in fP that have an inverse in fP, the inverse monoid invfP(NP) of functions computed by injective Turing machines with NP oracle, the monoid cofP of functions in invfP(NP) that have an inverse in fP, the monoid injfP of injective functions in fP; e.g., it is shown that the monoid cofP is finitely generated, and \\(\\mathrm{P}\\neq\\mathrm{NP}\\) iff \\(\\mathrm{invfP} \\ne \\mathrm{cofP}\\) iff \\(\\mathrm{cofP} \\ne \\mathrm{invfP(NP)}\\) iff cofP is not regular.","type":"string"},"datatype":"string"},"type":"statement","id":"Q666698$B3788AFE-79FB-4E10-9E0E-CDDDC61696C0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e1df29911c330da2d8d89435a35b182dae9e523","datavalue":{"value":{"entity-type":"item","numeric-id":589408,"id":"Q589408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$0E69FE67-A76D-40B6-A8A6-53CF2AF1AA7B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666698$2AA3946A-DF8B-4086-9307-20235AB53E20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4ac0e84a504a59b674a6c5271111dec0d2b6bb2","datavalue":{"value":"20M18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666698$1A9E33DE-979F-4127-8BB7-059D4370E18C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4912fa1f6079d284164e5c55a4de9722fc4d77e5","datavalue":{"value":"7034513","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666698$DF4DCD44-1704-402A-A9C4-0FFAB59E8006","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d13fcc32b7b99183682b8db5d55c1564a2758dae","datavalue":{"value":"inverse monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q666698$F33A88D6-4E4B-41E0-B9F3-84AB7EA77CF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834c45d526445b63ede129bf0252d3b47bed13e5","datavalue":{"value":"NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q666698$4A34D240-FE97-4808-B950-2B34FA1DFAE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a2b24f6056a67bc35da06909c9272de4feab241","datavalue":{"value":"one-way functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q666698$5F748A03-DC10-45AF-B623-A4B72CDDE18F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1af85c7b2f6fd07526dd5f6ad7e9d1c876779e29","datavalue":{"value":{"entity-type":"item","numeric-id":766115,"id":"Q766115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$810BF89A-7B65-4701-9AFD-1E016679EF39","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":"Q666698$13306A53-ED41-4333-A75F-91D0D74CFD01","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"44cea8ada5c45c31221620f88f3291540e14205a","datavalue":{"value":"W2594086588","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666698$D8F12E19-A7CF-4E74-9DBE-1ABE42E6C8AA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1366bd2322a8359118d05135af2e7062ee0ec3e","datavalue":{"value":{"entity-type":"item","numeric-id":5684240,"id":"Q5684240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$9F2B128E-FB07-4B05-AB4F-2330ED4BBFC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00eff4e1d7fe67e4cc0d1cfe53282cf9abcfe3d3","datavalue":{"value":{"entity-type":"item","numeric-id":3832041,"id":"Q3832041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$AD7C9C6B-E99B-4F38-9E88-8CCD23FFD319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8ab2eb789e29459b52d4529732a7d1aafecd457","datavalue":{"value":{"entity-type":"item","numeric-id":5246500,"id":"Q5246500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$D84E79D4-2F81-4DBF-AAB2-80A47EAB4A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5afbf744a209bae591f2001b963f84ed85dc6a7","datavalue":{"value":{"entity-type":"item","numeric-id":3848243,"id":"Q3848243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$E07652AB-C668-4BB3-8554-52971DCE431C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df0849bfc5839137425132014c5272d2ee494b1f","datavalue":{"value":{"entity-type":"item","numeric-id":4839155,"id":"Q4839155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$D6528C58-0770-479B-97BA-C887A2431981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef9791f4b37ee125203fd0d0075552c144cb2e86","datavalue":{"value":{"entity-type":"item","numeric-id":4162663,"id":"Q4162663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$6E484FB2-675D-48A2-862C-91E6B25B21C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2a0b468127c3522c5545f19cc6264b526a1e055","datavalue":{"value":{"entity-type":"item","numeric-id":5925718,"id":"Q5925718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$D33E9BD4-9D7E-4A14-804B-F8E4427271C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b728b2e2a9c0c505e1474cff8852bb6a6cc8257","datavalue":{"value":{"entity-type":"item","numeric-id":4537454,"id":"Q4537454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$6C307992-93ED-4334-B59A-608F643D4023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"704b67c0c7a5a44ff323d18e1363803acffd4565","datavalue":{"value":{"entity-type":"item","numeric-id":4071737,"id":"Q4071737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$01659DA5-8B41-4EC5-B3BA-1A15DC89FEC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd6a2ee4e62bbabd30a89fa5d4542078151787b4","datavalue":{"value":{"entity-type":"item","numeric-id":3720586,"id":"Q3720586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$24F40C26-34C2-41D0-8A98-8B5FE04F1FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47dac2d40343576b5b3d049703e489ef60d7fee7","datavalue":{"value":{"entity-type":"item","numeric-id":4023358,"id":"Q4023358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$56C9848F-71BA-4615-ABF4-BD09AD316BA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666698$34F5B779-63BE-4140-BB09-2687EDF9F27A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ea208a8cb98dedcd39a7283fe53caf059b06d932","datavalue":{"value":"10.1007/S00233-018-9990-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666698$E95E775C-4BB5-4E13-AEBB-A08982CED80A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd02a1d18cca0da10d9a5f50005743150177d8a7","datavalue":{"value":{"entity-type":"item","numeric-id":5246500,"id":"Q5246500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86efea84e4ca86531a58ae1826bfa42e48c79bd7","datavalue":{"value":{"amount":"+0.8310487","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$474AE029-3509-4F02-B1D1-30E830E4A1BB","rank":"normal"},{"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":"d865b5aab5ca829ff96029e84367f37f946d10a3","datavalue":{"value":{"amount":"+0.7536744","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$702439A2-0598-4F58-A8CB-AC80D631091B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9bfaac8f5c946443454587b8994cc2d26cc3c00","datavalue":{"value":{"entity-type":"item","numeric-id":5739486,"id":"Q5739486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64c654bcd1964dcda96ee4aa0fcac84e5dbe0710","datavalue":{"value":{"amount":"+0.7244521","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$212229DB-EEF0-496A-8178-361228A8A6FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a2a6fbed356ec3149470fb99a8146e2f2d07b03","datavalue":{"value":{"entity-type":"item","numeric-id":1064780,"id":"Q1064780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a8242be57b7aa8e062abc11b0bbc51e7eba1059","datavalue":{"value":{"amount":"+0.7036616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$7BDB5373-CBA0-415A-862D-50B7482DF5A5","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":"d08bb5e8808e858eb09115d4677125d90c5357a7","datavalue":{"value":{"amount":"+0.7018258","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$5A2C93E2-742F-4B2C-B7DF-1758959B163F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5745ce36f7950df377b00c22a360e79c90bb5b62","datavalue":{"value":{"entity-type":"item","numeric-id":3359757,"id":"Q3359757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d1ad8dd2b2bbc3d6417c97a9483b235d0660d97","datavalue":{"value":{"amount":"+0.69761944","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$ABF71C41-46DC-4664-8776-D9B478F9A994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cae77997bdeb4d479468a3bc19aef28e5ebdabd","datavalue":{"value":{"entity-type":"item","numeric-id":2154466,"id":"Q2154466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"175a51ef7daf84baf448afe12e62ffcb85a94818","datavalue":{"value":{"amount":"+0.69373727","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$53012845-4773-47EE-938B-FFF679CBEBB2","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":"17f312692f646caafb47612c93c3f006bb02927c","datavalue":{"value":{"amount":"+0.6923356","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$36E9E006-0932-4830-AFFC-086B247CA4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff174ac439be7c7b749ddc83cef7b2c570e2d9bc","datavalue":{"value":{"entity-type":"item","numeric-id":1096587,"id":"Q1096587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8eea29f56f6e7267c584f52449a62ebf9c2ab68e","datavalue":{"value":{"amount":"+0.68809557","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$68FFF54A-AF23-4C86-8210-1EA4A00496B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96ebcaf667929835cc49482d80e1924c71889ccf","datavalue":{"value":{"entity-type":"item","numeric-id":1877694,"id":"Q1877694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21816ee5bf6f07fdc2bf49bf8bb9670c5bbe1ace","datavalue":{"value":{"amount":"+0.68631303","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666698$2FD48487-89DF-4EC6-94FA-56BBB6582D50","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Inverse monoids associated with the complexity class NP","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Inverse_monoids_associated_with_the_complexity_class_NP"}}}}}