{"entities":{"Q4033836":{"pageid":6063568,"ns":120,"title":"Item:Q4033836","lastrevid":55231405,"modified":"2026-02-05T02:48:56Z","type":"item","id":"Q4033836","labels":{"en":{"language":"en","value":"The minimum consistent DFA problem cannot be approximated within any polynomial"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166345"}},"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":"Q4033836$2EEFD011-89EE-425D-BCBC-C9AF5EEC5712","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"76e8d01edf72a283ba09c72fe531a5c17dfabd3b","datavalue":{"value":{"text":"The minimum consistent DFA problem cannot be approximated within any polynomial","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4033836$E2C52FB8-3602-47C1-B6A3-717DBC0AE8B2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dcb875dda3f0a13a76c66f2835d85870cf0958e5","datavalue":{"value":"0774.68084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033836$ABA85F78-5A6E-47AF-92F7-F5A2ED54F506","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"769dca8afeeb5f62052d34bc0dd8c744745ad74b","datavalue":{"value":"10.1145/138027.138042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033836$A7340CCB-6C31-47D6-A84B-637C34CF636A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f1c45c99d7f66aca9a38e9b39a010fbe970038a","datavalue":{"value":{"entity-type":"item","numeric-id":676239,"id":"Q676239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4033836$51F38F51-C476-4E85-BEF1-5D76C682BA33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d42337cf24b90f5ac095f15e64afb2b57c10dc7","datavalue":{"value":{"entity-type":"item","numeric-id":391735,"id":"Q391735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4033836$AEA5B272-2168-429D-B7D4-9A1464541463","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f12bfc80fe4a431c556e028f5134a217234a7cc4","datavalue":{"value":{"entity-type":"item","numeric-id":63915,"id":"Q63915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4033836$EED4DB90-3138-41A7-B15B-4CA8A1733ACC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4033836$AE348071-8A28-4FB2-9F16-9457869B174E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033836$A929238E-6713-46B9-B02E-8E50D7B7778A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033836$02C72C81-BECA-45CA-BF90-66ABAEAFF796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033836$D3DB3B22-940E-4FE3-B9C0-E95705325E4C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"09ac4ac009755ccd55dfa802ce3711d5cd4fde3c","datavalue":{"value":"166345","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033836$F073D441-5605-4825-BEF6-79568FD2316B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b8a0e50914e1a9249bc0369e2fbfd33214adf69","datavalue":{"value":"reducibility and completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033836$00A0C8BE-85F2-4952-8F21-712F42A6326F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"422085fa539c12240d810b0c5f3bdf17ec999957","datavalue":{"value":"computations on discrete structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033836$4DEC7EE9-B9E7-462D-BCBA-2DB359F8E7A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033836$A843C172-2BFE-4F0B-802F-D13EB971A4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033836$FB696A5E-B13E-44CF-9C87-5048B9763692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b24d85df06f15d48eff2668d75804ca06bc7720","datavalue":{"value":"minimization of finite state machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033836$5356E042-DB0A-46BF-8909-C5AF174BE51E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83415edeafca56ab469840bac526f564659a0b3b","datavalue":{"value":"nonapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033836$D09A1938-AB05-4CBA-A6B2-AD1BFF451E30","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":"Q4033836$AC6F4151-DA77-4ADF-8CA7-D04B2D73B5CA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"257d3c9e6825c256fa3044a1c45aa9aa94f0941a","datavalue":{"value":"https://doi.org/10.1145/138027.138042","type":"string"},"datatype":"url"},"type":"statement","id":"Q4033836$C5112716-A9A7-4287-966F-DF8995EAB4A6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"24d778e6e2110ec82e10448ce03d79f796316436","datavalue":{"value":"W2074010768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033836$7C475D5C-3B8E-4976-A66A-5AAB4E6FAFE0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24b8c354005a1a37a222a4544e7751b98fc44e38","datavalue":{"value":{"entity-type":"item","numeric-id":2583554,"id":"Q2583554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"331a291dd3a860c73bc3991a589ee0a570f2ef25","datavalue":{"value":{"amount":"+0.87639319896698","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":"Q4033836$30E2742C-F9F8-481E-8CCF-C3ABF3EC9F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c59b997f99e82dcbe880c704e6c3d39c40442723","datavalue":{"value":{"entity-type":"item","numeric-id":2641868,"id":"Q2641868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f0304ec0a7983353e793b8df59e6b779cd917c3","datavalue":{"value":{"amount":"+0.862237811088562","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":"Q4033836$F73D4030-5540-4919-943C-337806670C3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51051b4c05bc494c71eecb5dbeddd247bf704652","datavalue":{"value":{"entity-type":"item","numeric-id":5710693,"id":"Q5710693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ec88b42bc3d346a94c99d29f60614afce7523b3","datavalue":{"value":{"amount":"+0.8575543761253357","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":"Q4033836$3CA63DE7-1AE2-48F6-8F99-3E6529B80104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52a4dae046f7af5d736416c2d03905873c402c91","datavalue":{"value":{"entity-type":"item","numeric-id":2182675,"id":"Q2182675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ad7398e656c7ce4707447dc6f4383d5fb5f53e6","datavalue":{"value":{"amount":"+0.8346736431121826","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":"Q4033836$A7EB0955-F0B3-4F9A-8EDD-0142AEB5FC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b14e7830d9ce6132f9c75b380e0ee0eea8d97500","datavalue":{"value":{"entity-type":"item","numeric-id":306711,"id":"Q306711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44e7d46cae2a1a1cb5727c7db298d33aa39439ad","datavalue":{"value":{"amount":"+0.8136857748031616","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":"Q4033836$E162BB0B-7F15-47E3-A57F-70F4BE080053","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4033836","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4033836"}}}}}