{"entities":{"Q1099613":{"pageid":1110365,"ns":120,"title":"Item:Q1099613","lastrevid":66130344,"modified":"2026-04-12T07:45:09Z","type":"item","id":"Q1099613","labels":{"en":{"language":"en","value":"A classification of complexity core lattices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4041261"}},"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":"Q1099613$27301A05-0EA0-4F62-9886-2E2DFB1F3A4E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6b37ff38e01036dbe81633f023d42bbd4e66904e","datavalue":{"value":{"text":"A classification of complexity core lattices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099613$CC19D9C8-D70A-4034-9815-97B8E09FB54C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5c863d31c67c18e527cd52d23aab8a2cde73e68c","datavalue":{"value":"0638.68033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099613$79E9A20D-1592-486D-B516-8E6C92A358D1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"200fc95a331958a29516572f949d60feca8d1b07","datavalue":{"value":"10.1016/0304-3975(86)90140-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099613$640B6A09-A043-4E15-BA2B-B9E22454B87D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a644df4a4e50751f0ed1cfeba15d4b2804901a7a","datavalue":{"value":{"entity-type":"item","numeric-id":395020,"id":"Q395020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$85F76997-20D5-49E4-9726-D0FB7E20991F","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":"Q1099613$F94548E4-2FBA-40C4-953C-99B92AC1CD7B","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":"Q1099613$81D8757F-37CA-4684-9A7B-80EC8A50FF37","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3b37498c3907e69f17689a3b54471d746bbb8d8c","datavalue":{"value":"\\textit{N. Lynch} [J. Assoc. Comput. Mach. 22, 341-345 (1975; Zbl 0311.68037)] has shown that every recursive set A not in P contains an infinite polynomial complexity core: a set of elements \\(C\\subset A\\) such that any algorithm deciding A needs more than polynomial time almost everywhere on C. Actually, any A not in P contains infinitely many different cores, the collection of which forms a lattice under inclusion. We study the structure of this lattice, proving that, surprisingly, there are only three possibilities: assuming the lattice is not trivial (which happens if A is in P), its shape depends only on whether A is `almost P- immune' or not. It is known that the natural intractable sets usually do not have this property.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099613$A9D4F081-69E9-4D91-B0C7-5B89C42B6206","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099613$20BD5A03-D8E3-4470-87C1-904E2E373B20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099613$E0C41A8F-4AA9-4A04-9406-E8C5DB84BF2C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d36474def942caaa6ac0371be26c1d278c001c67","datavalue":{"value":"4041261","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099613$BFFE288A-6502-4D66-9A8E-27F35447BA8D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efc04053771c816d6c8b781a521150d16d2e381c","datavalue":{"value":"core lattices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099613$BE577C51-CBAB-4A70-9166-468C659C2DE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60cfc573dadb9dc877ea2100ca1b8ce38089a579","datavalue":{"value":"polynomial complexity core","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099613$480F796C-8B49-454A-928B-5EDE6A266C7B","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":"Q1099613$D49BA208-155E-4E6A-AFD4-3C4C41DEBC1C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"317fb5fbe55d52b9bcfbb0d61124a5eb337b7f68","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90140-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099613$772D044E-2AE4-40B6-BB06-3323AA2F11E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"759e5dee944820157061f4e259c276cb3bb8476f","datavalue":{"value":"W1998915384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099613$9E258E1D-FDE9-4088-AF37-9C708085D524","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$B35A5F5A-A0A7-4688-8969-B6EAFDC2D4CB","rank":"normal"},{"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":"Q1099613$99680D1F-D7AF-4897-B867-4600008BB41F","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":"Q1099613$6558208E-1B45-441C-96C9-5EDC0146F921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad3c1482926510268eba646fdad04ccfee91af2","datavalue":{"value":{"entity-type":"item","numeric-id":1115611,"id":"Q1115611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$64138212-3D57-4AA9-A65D-F9250BDB56EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec2b4a5af183cf7ee7783a80345d09671a84367a","datavalue":{"value":{"entity-type":"item","numeric-id":3769964,"id":"Q3769964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$BE18553F-DDE0-4484-9A74-A83232E2F42C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91d507995080a0c1e8e38122d7102dcfbd332c5a","datavalue":{"value":{"entity-type":"item","numeric-id":4165427,"id":"Q4165427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$8CB07EAB-19D0-410F-9D99-27272905E1AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2bcba6abf24137e5ea317e56b32f617a34d2b1e","datavalue":{"value":{"entity-type":"item","numeric-id":795829,"id":"Q795829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$0C98BB6D-3DB3-42F1-91E8-9D0B5E3BC9A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$0AB98B71-013C-4C7B-AFAD-1DD0DE93B0FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25bc6d932f6af9eadec9ab4825895f5ea6edcb05","datavalue":{"value":{"entity-type":"item","numeric-id":4069780,"id":"Q4069780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$3B192282-4248-4E5A-8F9C-728EC90A0853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01fc2040ffe16ed03fdd5700cb1de1e73a3cea54","datavalue":{"value":{"entity-type":"item","numeric-id":3787474,"id":"Q3787474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$E5BFC379-4564-4B56-9A8E-07385FEB6703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50fcf5981ae589f600261cdff81132ea97e61a11","datavalue":{"value":{"entity-type":"item","numeric-id":3751007,"id":"Q3751007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$23093C0C-6ECA-47BF-8C30-13576F9CBF67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bde708178fd22b5a6473ace4f76c9d9acbc0b80","datavalue":{"value":{"entity-type":"item","numeric-id":3347296,"id":"Q3347296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099613$E0F24A63-3589-4A69-84F9-A2338305EFA3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fca234c6cd7248dad4be715e9ebd3c8ff2b7fb1","datavalue":{"value":{"entity-type":"item","numeric-id":3219763,"id":"Q3219763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d635293995f5810f48c3d8dabecaa35d914f042e","datavalue":{"value":{"amount":"+0.9069263935089112","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":"Q1099613$3B4C5468-710B-45A7-8A36-1A77DE3DE651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a93f3254dee7595df34bb2022169bea4b5977c71","datavalue":{"value":{"entity-type":"item","numeric-id":3789542,"id":"Q3789542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9aedc75cf3652cf0e8b02caa42bcd7ebf01f3125","datavalue":{"value":{"amount":"+0.8699628114700317","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":"Q1099613$C3459241-C1E1-4486-A0EF-C7867EA6C8B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d71d7948e0f1c5c6fdb4011e20ab67860753a3c2","datavalue":{"value":{"entity-type":"item","numeric-id":3751007,"id":"Q3751007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d85fd05b814b5fb99b6a2a5c7e4b355bda485e0","datavalue":{"value":{"amount":"+0.862235426902771","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":"Q1099613$607011FE-E348-4877-B2F3-CE11B22E3654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6c07449b1a3d844de5f6dbe6b57ce0296d627c2","datavalue":{"value":{"entity-type":"item","numeric-id":3690221,"id":"Q3690221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5caf6f68f8f31665d952ab774bd61617b4ef6ab6","datavalue":{"value":{"amount":"+0.8265951871871948","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":"Q1099613$AFA7F011-D7D6-4686-B2BB-2541AD5348E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"505342e9ffa01230f62acf168a29bffe6be05925","datavalue":{"value":{"entity-type":"item","numeric-id":1115611,"id":"Q1115611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59a75d188050da3d29f5f1ce7ede109af5b15035","datavalue":{"value":{"amount":"+0.8119459748268127","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":"Q1099613$26EB44AB-8202-444F-9996-274160D5564B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A classification of complexity core lattices","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_classification_of_complexity_core_lattices"}}}}}