{"entities":{"Q2941635":{"pageid":2952355,"ns":120,"title":"Item:Q2941635","lastrevid":79833947,"modified":"2026-05-06T14:48:51Z","type":"item","id":"Q2941635","labels":{"en":{"language":"en","value":"On the NP-hardness of approximating ordering-constraint satisfaction problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6474895"}},"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":"Q2941635$8B32B845-27D4-4000-B493-31B88185523E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"08a1a2ce6baf2c654c50dce3df99ee6e14a6fa36","datavalue":{"value":"1335.68094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941635$47AD4712-1A81-489C-9896-1FDCC300D1F1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dbd0b695fb6fcafddaf81878c9443c3ab8191ffa","datavalue":{"value":{"entity-type":"item","numeric-id":626618,"id":"Q626618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941635$1D986BED-1ED2-43DB-A2C4-7A9252F76D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"61d67f4d3d13702c071976c302b7c2e72d7d7414","datavalue":{"value":{"entity-type":"item","numeric-id":1671995,"id":"Q1671995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941635$ACE62660-F2DA-49DD-ABEC-9D782E4C7511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"668dd6d72a9173f330635d53a8087b2defbb17f3","datavalue":{"value":{"entity-type":"item","numeric-id":386992,"id":"Q386992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941635$651D669B-33C4-40F6-88A6-EAB910086F93","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"11632bef515b8b0af0e8d65098d262d28b5f8c42","datavalue":{"value":{"entity-type":"item","numeric-id":2816408,"id":"Q2816408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941635$D3CEFC7B-68AC-4C9B-B39C-0AB54FCC26E4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e463a3f76b72914d69100f109f02e2f624263f82","datavalue":{"value":{"time":"+2015-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2941635$D6A3AC7B-1613-4086-92FE-FFCC4FDD4AFA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941635$93DE9B0C-F9D5-4749-BECE-259D584229B3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bd6c865c4cb387c4aa66d02cdf7e374a7e5e8794","datavalue":{"value":"6474895","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941635$F137D0BB-44A1-4A9A-9FC1-94A683C28C43","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d466b65980aca95b261db98ce5eac364340eb6ef","datavalue":{"value":"acyclic subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$7875E240-5D67-4769-9E8B-320F4946DF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0e0eba10f1a5febe408e3aacdacff94f6aa83e9","datavalue":{"value":"approximation resistance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$DB70BCE2-0AA4-4670-9473-4DE9E08F28D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da45be5faf9a3549aefe4dbe9a083b6cf1f315ef","datavalue":{"value":"betweenness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$252458B7-76AD-46C5-9AEE-6171FF873F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00fab533cd38d922e3a2c54a153ccdfb1b56ca89","datavalue":{"value":"constraint satisfaction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$379804AA-7498-45D0-BB6F-0BD15D96718F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b5048130fc8a077762f5790a9ac4131fca3087b","datavalue":{"value":"CSPs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$9264C687-CCCE-4DEB-AAE2-4F1FA633E3ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d55d12d8e521239dbfda14f4fd78e26c893c51bc","datavalue":{"value":"feedback arc set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$65770CA9-4DD5-452E-B89F-700E616F7142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5f619d7196488e93cc39b118f923aa8af49a90e","datavalue":{"value":"hypercontractivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$27CB2F26-DB00-4F25-8362-4B36CD1A49A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$C46D1A6A-5A19-43D8-811C-F18E273664AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c55aaa92cb4d7883b510c8490c97c8b2db3cdf84","datavalue":{"value":"orderings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$EA880414-7C52-4CCD-A413-BEE67E05C7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cc98c0e2174d7de95e927b0d5314a0a6dd6a1f8","datavalue":{"value":"PCP","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$E0B5B1F8-797E-49BD-84D0-3953BEED4019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"198526b3e16365d088b0d8e8cb1a48a9c3937632","datavalue":{"value":"probabilistically checkable proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941635$E52545DF-3BDC-44DE-8545-6DD87E2A6115","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":"Q2941635$ED59CBDA-F52E-4724-A94C-9560740C8585","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba11a1357fcaa51587355b9089894f5840a1a8cb","datavalue":{"value":"https://doi.org/10.4086/toc.2015.v011a010","type":"string"},"datatype":"url"},"type":"statement","id":"Q2941635$6CD2F094-2ED4-4B9C-A46E-8A0E0097AE69","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1ff9f487fd0088a5d80df38f10154f5fcf0357ce","datavalue":{"value":"W1593375062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941635$06E81E23-3944-4477-BA22-5FCA432A2A10","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1a59b9106a5dd5105f2bc476300c4cdae45ec3","datavalue":{"value":{"entity-type":"item","numeric-id":3579218,"id":"Q3579218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941635$011F8E5C-11E7-4C10-88EF-7A69ABB45362","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d2292fc239f2e99fcaf62d72a3dd68f0d88770e3","datavalue":{"value":"10.4086/TOC.2015.V011A010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941635$D206AB3B-B895-4EFB-99FC-C8A9F0D134C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c33177427642ba51ea3fd02ed386f647ab23929","datavalue":{"value":{"entity-type":"item","numeric-id":2851846,"id":"Q2851846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab7b5389e8f9f799da3c4a8eeb1386958fcf8641","datavalue":{"value":{"amount":"+0.973007082939148","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":"Q2941635$341D0DF5-5DD9-4803-BB22-976CCAE78EF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c43b957d5009e6e97781bd399025f6bb4dc43b3b","datavalue":{"value":{"entity-type":"item","numeric-id":3093627,"id":"Q3093627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9ffbfac8010d87f480d88b7e2f7e4b2afc9ee0e","datavalue":{"value":{"amount":"+0.8897005319595337","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":"Q2941635$A9A27D11-9D1D-4A49-9679-80306B6A8CFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9af513d149e3818a7b4062c6733ce12baf713344","datavalue":{"value":{"entity-type":"item","numeric-id":3167393,"id":"Q3167393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"109bafb5d097d60b8ebdd77b24875d2d193c56d1","datavalue":{"value":{"amount":"+0.8070339560508728","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":"Q2941635$BEF76CC0-9A84-416D-B93A-9AB5B7FEC023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e4faab94e764ca441771d56eb4cf85b829b42d9","datavalue":{"value":{"entity-type":"item","numeric-id":3499775,"id":"Q3499775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79ba8e8f977ff2760fde95837b28780833243110","datavalue":{"value":{"amount":"+0.7874768972396851","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":"Q2941635$3F19E588-DBB9-4280-8436-600572886EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bb1af61f4a345d12c7eed4e47a0dc87f2407298","datavalue":{"value":{"entity-type":"item","numeric-id":837178,"id":"Q837178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"133591ffe2ba0e3cefcd3ff3cc4f614397bcdbb4","datavalue":{"value":{"amount":"+0.7816461324691772","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":"Q2941635$15F101E5-D0BA-4502-8BC2-AC200F60ADCE","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941635$E07668EF-F765-4ABD-9464-CD8BB0E9A22F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the NP-hardness of approximating ordering-constraint satisfaction problems","badges":[]}}}}}