{"entities":{"Q1109766":{"pageid":1120515,"ns":120,"title":"Item:Q1109766","lastrevid":49211614,"modified":"2026-01-06T18:51:23Z","type":"item","id":"Q1109766","labels":{"en":{"language":"en","value":"Collapsing degrees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070878"}},"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":"Q1109766$E4FEEF19-17C5-4143-9640-D265A9942D7C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"26a5311489b89c887d8bab339559268f9675aec6","datavalue":{"value":{"text":"Collapsing degrees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109766$AF261309-F71F-44AF-A1F1-5008297488BC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"964eaedc87d00d570d4ee415b1d59eb0264b8bb6","datavalue":{"value":"0656.03026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109766$1A642836-4D3C-4968-80A2-A3CDC74AEBEF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cd81882fb0c9a8dfc46c7fc78ea2d9d12fab9706","datavalue":{"value":"10.1016/0022-0000(88)90007-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109766$6B783C68-E370-4C42-B5E1-E35BAFD0ACBA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c50a503249816ae6bfc9a4fea05a1fa1163cd7c","datavalue":{"value":{"entity-type":"item","numeric-id":913488,"id":"Q913488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$C301F588-08DC-42CC-8912-60D9C7993EB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a7e0e583777a7db2c621a28e82e48787e5c6230","datavalue":{"value":{"entity-type":"item","numeric-id":1109765,"id":"Q1109765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$67976D4B-48DE-4C17-A723-0FCB6F1CE570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bdb4109ac59d3ca813b07e527a14abf4f26a17c1","datavalue":{"value":{"entity-type":"item","numeric-id":579919,"id":"Q579919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$BE337A74-C724-4F75-A286-58F4E076D97A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$6EAB22FE-69B2-419D-BB53-57DF93312302","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1109766$8F872C8F-2897-44AC-9FAF-CFCD31D5070A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e8738bfaf83b29541ee1bea7a8dfe84e15df847","datavalue":{"value":"An m-degree is an equivalence class under polynomial-time many-one reductions. An m-degree is said to be collapsing if its members are p- isomorphic. This notion stems from the well-known conjecture of Berman and Hartmanis, which asserts that all NP-complete sets are p-isomorphic. Much work has been centered around this conjecture and both ``pro'' and ``con'' facts emerged (see the introduction of this paper for an excellent, clear and concise survey of these matters). The paper is a valuable contribution in this area of structural complexity. It provides the first examples of collapsing degrees. Thus it is shown that, for each set A, there is a collapsing degree which is m-hard for A. Also, a collapsing degree which is 2-tt complete for EXP is constructed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109766$A45B5E60-002A-41BD-8E6C-D82AEE733A64","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109766$843E6C09-A17D-45CE-B47C-DCB4ED7E2A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109766$5254E2D2-FC74-4C65-AB77-253104482DF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109766$9581F384-E74B-40E0-8E1C-542EF5BBE70E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b04a67ae646787d4a35d381dba7b256a90a8931","datavalue":{"value":"4070878","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109766$EBAF335B-FA9F-4A0C-9637-918DA418259A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b84579a944606673e187f13c31298a6cfe7c9c1c","datavalue":{"value":"polynomial degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109766$C7839E74-E2E9-4627-9F3A-99823079DC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51206d8c8e7e1f58220b3511816c17b99b144b85","datavalue":{"value":"p-isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109766$53AECE02-8690-4106-AEBE-31999AD5676C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b9523b81abac7dcf2946305ecf06ced9bb8e7c3","datavalue":{"value":"structural complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109766$88AF27AD-D321-437A-A1A0-17504236B42F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f06ad48c81f208495290ee86b2d8f76c534aa58","datavalue":{"value":"collapsing degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109766$27820929-13C8-46DB-AD8B-1528784FD2D8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fc8522c6547fe483c0d1ae4eec1b8d9306e5db1","datavalue":{"value":{"entity-type":"item","numeric-id":290243,"id":"Q290243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$32EB1020-8D9F-4A67-AEE2-315EDA33D671","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":"Q1109766$EE89806A-252E-4EF2-AA36-D4C02136359E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d040ad691897a2f1b676065711a412804a91dadd","datavalue":{"value":"https://doi.org/10.1016/0022-0000(88)90007-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109766$0CF18B06-D690-4664-AE13-D754863148AF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5d4375ae719eebd095f6d1a92d864648fdba1bd","datavalue":{"value":"W2293017760","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109766$6199A0C3-3A6A-437F-A755-26C1245855CE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"22d609e74c7776220c6107d8f9688121ff977e92","datavalue":{"value":{"entity-type":"item","numeric-id":3747726,"id":"Q3747726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$DBF8CFB7-F543-4184-BAC2-6FDC6ABF3E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$5FC42394-CDBB-4271-9D28-C873A8512AD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4553a412b4b55bb167272479a5aca159281f2c2","datavalue":{"value":{"entity-type":"item","numeric-id":4160434,"id":"Q4160434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$CCF21743-106C-43BC-9222-DC757154914D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79900a6e52bbf30550325548a458c4abb252a3f7","datavalue":{"value":{"entity-type":"item","numeric-id":3686040,"id":"Q3686040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$92284E5E-5804-4503-9558-97C1FFC63AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2e90f9104ea022c7422408156c4aea89597a34a","datavalue":{"value":{"entity-type":"item","numeric-id":3686043,"id":"Q3686043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$1DF186D0-385E-410E-BD42-03947C2FBF43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dae26af80a5696fa8c01db658b71f7ff80167bbe","datavalue":{"value":{"entity-type":"item","numeric-id":3248015,"id":"Q3248015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$53D5F599-4F56-4BD7-B405-37B9CBD5DD07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16224d4d737bf6a907fd00473a3903d2f3777c0f","datavalue":{"value":{"entity-type":"item","numeric-id":5180402,"id":"Q5180402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$355F43B6-C4F3-4145-BC1D-9833A0620712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cff01e63bd23c00afc50b886c3b7f358448e969e","datavalue":{"value":{"entity-type":"item","numeric-id":1099614,"id":"Q1099614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$340779C8-3C91-4A55-98EE-28D18C921955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$9364B96B-B3E0-4376-8E1B-0D9304D639F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb51cb599580481aadcbb3a7e805e65dbcbf5ce5","datavalue":{"value":{"entity-type":"item","numeric-id":1079364,"id":"Q1079364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$D71A38D9-C43F-4261-81EC-D7E43BD7340E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5729674352df42afcb3727df7e5bbb4c13eb877","datavalue":{"value":{"entity-type":"item","numeric-id":1097694,"id":"Q1097694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$97826E96-F73F-40CD-A208-568C55CB028B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$7F274D5C-FAAF-4BD9-99FB-E4C66D741B41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$0CB22D05-D606-4250-A9E7-CD9B567096FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c19040a60a44db62995cb08427466942d64d95f5","datavalue":{"value":{"entity-type":"item","numeric-id":1077412,"id":"Q1077412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$A38D2F26-4261-4799-A789-2D72CC46457C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"850ec53483c087fa2e8890fc924e571da7793c17","datavalue":{"value":{"entity-type":"item","numeric-id":3232283,"id":"Q3232283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$306D5923-DFF2-4849-B614-D3219E9A0A69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0c451ae4bc57a2401ca0a06eefdc1ba5da11477","datavalue":{"value":{"entity-type":"item","numeric-id":5848891,"id":"Q5848891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$D834005D-1AC5-4D28-992F-B30DDDDCDB91","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":"Q1109766$7D661069-9224-4E9B-B846-916CF0ECDC4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1edcfc8f162dce621803913f4363a765362e71d8","datavalue":{"value":{"entity-type":"item","numeric-id":3819052,"id":"Q3819052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$643F1C43-F159-4777-8D27-4A4AA2FDAED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f17a7f319117d5a44769bf519f74a5e5ddbffa2f","datavalue":{"value":{"entity-type":"item","numeric-id":1068536,"id":"Q1068536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$7ECAC66E-09A5-430F-A38D-821D5D77DD9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"394deeefbb755cf976a8a03c7c7a6175be540a9f","datavalue":{"value":{"entity-type":"item","numeric-id":5547582,"id":"Q5547582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$246466E2-5C2B-4BD5-A326-950035A0D2DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d54907135ff5413bb27294f15143b5bc86d7a143","datavalue":{"value":{"entity-type":"item","numeric-id":5723170,"id":"Q5723170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109766$1AF3DAC4-66A0-475A-AED0-C2CE6243A64B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b57a8a7a3aa8afe0041511c31bc104b5bebd035c","datavalue":{"value":{"entity-type":"item","numeric-id":4944898,"id":"Q4944898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afd053f96a61602ae271c985c0fc1294d7dd4e27","datavalue":{"value":{"amount":"+0.8824320435523987","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":"Q1109766$CB864631-C494-49EE-BA6E-BB20A11DDBD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99b8c5a6cb0946a8391a380e2761b173681d883e","datavalue":{"value":{"entity-type":"item","numeric-id":4036580,"id":"Q4036580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d02a879989294ea24f11b5b58f2ecec3ed19a2c2","datavalue":{"value":{"amount":"+0.8719439506530762","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":"Q1109766$18B9B1AF-2114-421E-8373-6EC3CA696482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c321227ef9aff13cc8f9f7cdd81acc7dc0ff0b0","datavalue":{"value":{"entity-type":"item","numeric-id":4841303,"id":"Q4841303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"709a110190672242bbe4b75300984adf701087cf","datavalue":{"value":{"amount":"+0.8664456009864807","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":"Q1109766$7FA51E1C-4378-4D2D-A24A-703D52B6DF13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c127f3f6e973dccc221fc9ae4ccba7aa1b4b943","datavalue":{"value":{"entity-type":"item","numeric-id":687510,"id":"Q687510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"152de05900087abeae8b82bb357a3f96f06c1d24","datavalue":{"value":{"amount":"+0.8319812417030334","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":"Q1109766$57D39B2C-507E-41BB-99CD-4E6276D3DD06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b93b3d487189ac0148052e9bc9a5ffed1dd0ef2","datavalue":{"value":{"entity-type":"item","numeric-id":2366690,"id":"Q2366690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a8ff7d93f63b02fcca128da67987597686aadb7","datavalue":{"value":{"amount":"+0.8285788297653198","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":"Q1109766$08612F69-1072-4DD4-B41C-CDFDC2ED7FD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1109766","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1109766"}}}}}