{"entities":{"Q1344247":{"pageid":1354986,"ns":120,"title":"Item:Q1344247","lastrevid":81170030,"modified":"2026-05-06T17:53:51Z","type":"item","id":"Q1344247","labels":{"en":{"language":"en","value":"Deciding Frattini is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 720844"}},"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":"Q1344247$045AF609-852C-4EA8-9C28-E2761C4B7D44","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"56ab039d257930904756609fc41c5b81dfecab54","datavalue":{"value":{"text":"Deciding Frattini is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1344247$611CE518-D667-43F1-B0D2-8CF69FF4ACE2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0efeb33a650a52e28ecc5fdb07d461759d22728e","datavalue":{"value":"0819.06010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344247$9CF01C23-D3CB-4CB7-8EAD-2528D68B7795","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2767ba3a741e49ba2a2938067acf7b2172fde33f","datavalue":{"value":"10.1007/BF02115815","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344247$AB351129-E972-49DC-8535-174F6E560414","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5547c5f1a1588afdd3bee1db2968c1c3171e11a","datavalue":{"value":{"entity-type":"item","numeric-id":1344246,"id":"Q1344246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$93DBCE8C-82B8-4B48-BB32-76058DD0096A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e4fb9ce568de3750e3a2b86aee4348766bb9ad4","datavalue":{"value":{"entity-type":"item","numeric-id":1837217,"id":"Q1837217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$867C0003-3950-446A-927F-EB219B3C0E19","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$7F28723B-36BE-4AA9-B43B-01468B406872","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"307580e22f2d20de23b936c4fce7539a5342cbe9","datavalue":{"value":{"time":"+1995-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1344247$C7C3456E-DA77-441D-B8AD-7A494442E01E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"065ea7ad0abc916b5de3d5cb19edd72a9a6cfe40","datavalue":{"value":"The Frattini sublattice is the intersection of all maximal proper sublattices of a given lattice. Every lattice is the Frattini sublattice of some lattice [\\textit{K. Koh}, Algebra Univers. 1, 104-116 (1971; Zbl 0237.06006)], every distributive lattice is the Frattini sublattice of some distributive lattice [\\textit{M. E. Adams}, ibid. 3, 216-228 (1973; Zbl 0288.06015)], and there exist finite distributive lattices not isomorphic to the Frattini sublattice for any finite distributive lattice. The finite posets arising as Birkhoff duals of finite distributive lattices are called finitely representable [\\textit{M. Abad} and \\textit{M. E. Adams}, ibid. 32, No. 3, 314-329 (1994; Zbl 0808.06014)]. The main result here states that it is NP-complete to decide whether a finite poset is finitely representable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344247$6B9B84E0-E3C0-40C5-95C5-5C028C09F961","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ce5b74470053f031a57488d42a2b289573daad5a","datavalue":{"value":"06D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344247$D3012253-1BB8-4A4D-B519-F53EF59C4091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344247$69856320-75F6-4500-967C-3D7D7B8607FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344247$FFDFA5D8-1049-4AC0-BBCE-2BF831667E79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f7490696d9da8be70baf68448014bd46443abf18","datavalue":{"value":"720844","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344247$6C6A0019-2D02-4E56-AFBE-55CC41006632","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344247$64FE676A-5123-4AAA-93F9-29031867F7E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6de5cab25493477c271824feef256c73a75356e7","datavalue":{"value":"finitely representable posets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344247$126D0E1A-3C70-4CF3-BF07-BD3DFFDA8A68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63020a4e90928fd27618b8f3bae59c2a21b257dd","datavalue":{"value":"Frattini sublattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344247$67A6DF94-3EF1-49EF-B32B-7088348D8890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"713ceb79a10f8309ceb9a2e4a915c2f3d6536608","datavalue":{"value":"finite posets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344247$7463F40C-29CE-41A5-9B96-5A0FDA2DAEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4caf54cdaeb06c193adc180035f58f209b6ad536","datavalue":{"value":"Birkhoff duals of finite distributive lattices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1344247$DBC29D06-B35C-4785-9207-44FDDCC0A7D1","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":"Q1344247$E26C7F2F-B1CA-4F85-A47D-8F3EB74442EA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"63c4206ac0f3ed98531e41ea9d389184aa0400c7","datavalue":{"value":{"entity-type":"item","numeric-id":1338948,"id":"Q1338948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$CCE544EA-1A24-4486-B2F0-762F4DB41964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c328ff5a1104b2b229e3c05d4cd725d44f09af9c","datavalue":{"value":{"entity-type":"item","numeric-id":1846445,"id":"Q1846445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$45828890-1782-4ABD-BC53-3024EDBA6EB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"030c790659387a3543a2c24a8af5abffc9d4c203","datavalue":{"value":{"entity-type":"item","numeric-id":4175317,"id":"Q4175317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$2AE2CA19-6154-4D20-8EB9-69A2FFEBC585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c54c140dcad11275a149ad307301d9eba55857d2","datavalue":{"value":{"entity-type":"item","numeric-id":1219311,"id":"Q1219311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$BF1E086A-1D42-41A2-B64D-89014CE10877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43c16a177adb4c2437494afa2fdcacac21558f4","datavalue":{"value":{"entity-type":"item","numeric-id":1226111,"id":"Q1226111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$8FAEDBFB-A4F6-4201-88DD-664E91B8349A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77228b85c1f27bbf1d343133dc347747837b26d4","datavalue":{"value":{"entity-type":"item","numeric-id":1183950,"id":"Q1183950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$3F25E1F2-4979-4E39-BCAA-42BBCF5296C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d4dd4faeed82b17a31b15b4f4a630199ca52442","datavalue":{"value":{"entity-type":"item","numeric-id":4692885,"id":"Q4692885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$E105DD74-836D-4209-A31F-813AB3BDF1B3","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":"Q1344247$D7E37840-9B38-4006-B31E-80D3455512B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4040fe750a66c10734b415667ad021ea6782b4a","datavalue":{"value":{"entity-type":"item","numeric-id":5814847,"id":"Q5814847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$8EAA1A24-6F93-45BD-A6BB-6EA882B659F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e398aab5e1e56ed04f6487bee24704a5fd2b7ced","datavalue":{"value":{"entity-type":"item","numeric-id":2552512,"id":"Q2552512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$00D91798-8A28-43C4-98B1-51E6FBF3C920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1929790dda222fc6491a36e111410ba3d6785a2","datavalue":{"value":{"entity-type":"item","numeric-id":1132904,"id":"Q1132904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1344247$7A462A33-DC3A-4B90-A2B8-E7B713B71840","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"429838219ad6d0d42aad0599a743780506eeea58","datavalue":{"value":"https://doi.org/10.1007/bf02115815","type":"string"},"datatype":"url"},"type":"statement","id":"Q1344247$B6EBA14C-CDA3-4F18-A001-9B2F05DFD3B0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ecb5ef759958fa2c45bedb56c3d082afd4bf58a6","datavalue":{"value":"W2014049130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1344247$2AE6D59C-3E4A-4A7D-BBDF-73958757D7A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4488979991ec295400f35cf9cf3e42532868e5be","datavalue":{"value":{"entity-type":"item","numeric-id":1338948,"id":"Q1338948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6bb1a60a84ca2e719241f116e261ce844e02089","datavalue":{"value":{"amount":"+0.7951000332832336","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":"Q1344247$B367AD1E-BC65-4717-BE12-2B46CB322C66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db42e6e7253489f23b1db4f6c5de1723f4e0bd05","datavalue":{"value":{"entity-type":"item","numeric-id":1272243,"id":"Q1272243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f326e9b3a65fb1fb5e88df1964fb094d75971ff","datavalue":{"value":{"amount":"+0.7452805042266846","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":"Q1344247$7D7B9916-9DFC-444E-BE96-5287C7F62067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ae7b74cadb9fc39c22553984c704005b6e2e37f","datavalue":{"value":{"entity-type":"item","numeric-id":1908932,"id":"Q1908932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a44a0f478d6db31473e4aceffafa2dba50971421","datavalue":{"value":{"amount":"+0.7452801465988159","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":"Q1344247$AF064551-83DE-481D-91E1-920F6CD6ACC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57707ed3cbcdeaf27cb8af5cbbdee9ebadb917bc","datavalue":{"value":{"entity-type":"item","numeric-id":4361780,"id":"Q4361780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a045f26b6ef3b2e28de791096259ae5fc9609775","datavalue":{"value":{"amount":"+0.7290639281272888","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":"Q1344247$29559E0A-7DB0-4488-BDF4-2B06CF2F84CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02be8cc86ad72d171767f9a6d011140c4e5a8758","datavalue":{"value":{"entity-type":"item","numeric-id":3783337,"id":"Q3783337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45503141b12c73576bfee6bee402a9410b15affb","datavalue":{"value":{"amount":"+0.7249364256858826","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":"Q1344247$6C9CA81F-0D6F-4BB6-AD86-95EAFA455986","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deciding Frattini is NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deciding_Frattini_is_NP-complete"}}}}}