{"entities":{"Q452481":{"pageid":454248,"ns":120,"title":"Item:Q452481","lastrevid":77775692,"modified":"2026-05-06T10:01:50Z","type":"item","id":"Q452481","labels":{"en":{"language":"en","value":"Complexity of partial satisfaction. II."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6084849"}},"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":"Q452481$B6BAA31C-12E0-428A-982E-4BF461E1C225","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fd9c86ac18aac380f50da2cbd6dea6d47225a011","datavalue":{"value":{"text":"Complexity of partial satisfaction. II.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q452481$6B165680-711D-483D-90B3-1F2F6C15BC57","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"24f65f0c50933fd90adf4d817121dbfd06b01941","datavalue":{"value":"1283.68165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452481$23812764-69F8-4A8F-BE50-E223DA70002B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9594fe7a799b5bd92c9ddbc07292354debfdbf39","datavalue":{"value":"10.4171/EM/202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452481$43201C89-0E39-4A45-9D7F-A13AD929B011","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f66ee2af3b08178db65aefad8e74532367197ea1","datavalue":{"value":{"entity-type":"item","numeric-id":452479,"id":"Q452479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452481$2FB19991-735E-4EE2-8FD9-D8D1966AA300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d2b40f3f3240344357a908954aaa92ce342cab92","datavalue":{"value":{"entity-type":"item","numeric-id":6482151,"id":"Q6482151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452481$41306CF5-CCD3-4601-96B2-1A92EEC21A43","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"255223deab9a614645300983eff9e9b445f432d0","datavalue":{"value":{"entity-type":"item","numeric-id":207920,"id":"Q207920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452481$91DDA9F4-7833-4677-8D75-3AC78F8C9F01","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9be54b5bf8411b172b987b968e66cf4985f4b2f8","datavalue":{"value":{"time":"+2012-09-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":"Q452481$EFAA7884-EC3B-4A74-9D08-297221486CAA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9fc1be678d4d65e07d4ea1ac615ff673e2c98160","datavalue":{"value":"Summary: What is easy and when does it become hard to find a solution of a problem? We give a sharp answer to this question for various generalizations of the well-known maximum satisfiability problem. For several maximum \\(\\psi\\)-satisfiability problems we explicitly determine algebraic numbers \\(\\tau_{\\psi}\\), \\(0<\\tau_{\\psi} < 1\\), which separate NP-complete from polynomial problems. The fraction \\(\\tau_{\\psi}\\) of the clauses of a \\(\\psi\\)-formula can be satisfied in polynomial time, while the set of \\(\\psi\\)-formulas which have an assignment satisfying the fraction \\(\\tau'\\), where \\(\\tau' > \\tau_{\\psi}\\) and \\(\\tau'\\) is rational, of the clauses is NP-complete.   For Part I see [the authors, J. Assoc. Comput. Mach. 28, 411--421 (1981; Zbl 0456.68078)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q452481$EAE4122B-6406-4675-B5BD-E30E1BFBD2E2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452481$C62E8BE7-9B3B-4D20-9BC7-51024597BBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452481$EC84E953-BF25-4AC0-8D21-F58B02E7EB33","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"053a9c33c9ba036580958f4e3b031bff9bb0851a","datavalue":{"value":"6084849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452481$3F07A9E9-57DF-4701-A1F1-9D8DBCBEEE8C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q452481$7B841AEB-749F-454D-81C0-43DACB6B7384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4881dceebcfc2cfaaf48b0eeca275f318bc3a7ae","datavalue":{"value":"hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q452481$3E8EB38A-DFF3-45F9-B065-8C9B88BC8487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ec272a6895f1d9efbde6f9c4fc0d133355fbf00","datavalue":{"value":"maximum satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q452481$C52A60A8-5034-4076-AB21-86443EAD5A50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q452481$E2F608EB-F551-486D-9ED0-ABDB0D3A5480","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"27ff103bd8160549373d26dd284936580d02d6af","datavalue":{"value":"Q106019114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452481$F1070C31-EDC9-47A9-9D03-B74EA74DE8F7","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":"Q452481$64392A04-3950-4CD0-9071-389D80B5EE30","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b937cff77f3008ec75c747bc39da74a24ad81205","datavalue":{"value":{"entity-type":"item","numeric-id":3906440,"id":"Q3906440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452481$76E32E70-B801-495F-91C9-9B8867E7EF0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e102855d78129e98165e69c7b981008f149840c","datavalue":{"value":{"entity-type":"item","numeric-id":3956421,"id":"Q3956421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452481$B337FFF2-F24C-4DC1-B0BD-D4F76AE03555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452481$CFB9B8B4-2FDE-4C2C-B4ED-5306D4CF5C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64eca57a292fb535c64f0ee00c7747458afe5823","datavalue":{"value":{"entity-type":"item","numeric-id":4652606,"id":"Q4652606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452481$C5031A1C-B19E-47BE-86BC-4A5A59863EF3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d5b8b337426c2b1bb4fa759af1b3e76718c387ab","datavalue":{"value":"https://doi.org/10.4171/em/202","type":"string"},"datatype":"url"},"type":"statement","id":"Q452481$F8C0F2A7-CD55-4DBF-A1D7-698F47623E65","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"00b1e4173bbe66697fddfdca5767319f439963f1","datavalue":{"value":"W2070114427","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452481$967B96A5-5168-433E-A4D1-C3FD96E5FF3C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24ec9455f54c32283ad7953bf6c8ed6237e5816a","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39200e8f3d3a5b82b9a653d50c08b81d854c609b","datavalue":{"value":{"amount":"+0.8258876800537109","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":"Q452481$8E457C27-D00C-402C-B8EE-2BFA31E975C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df684ab8201b649acc8d339dca420dbf8bf70615","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9db8d4810d3e76c1b34757c330a98963efc2191","datavalue":{"value":{"amount":"+0.8209488987922668","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":"Q452481$3446DA0F-F3B9-4638-9B79-02771923FB86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5df8067314dfa8dec77f08c98ec8630779dcefc0","datavalue":{"value":{"entity-type":"item","numeric-id":960525,"id":"Q960525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ba351122fd4bc44b65da57b9f73a79c707b5ceb","datavalue":{"value":{"amount":"+0.8073792457580566","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":"Q452481$98506851-7E05-4CAD-8964-9556DC711A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45d8891ac6df97a878ccf7a91e4948e04efd55f0","datavalue":{"value":{"entity-type":"item","numeric-id":293164,"id":"Q293164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28852404fb0600b30d555f7e3ef38b9ee06ed9e4","datavalue":{"value":{"amount":"+0.8063292503356934","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":"Q452481$DC53F87E-A25E-4A62-B528-2BAF0DF05384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cc356a18244e2efa65bc6e99caf8f44b86aa243","datavalue":{"value":{"entity-type":"item","numeric-id":4286227,"id":"Q4286227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8299257f96a9845db293ff83319e26370d4525e9","datavalue":{"value":{"amount":"+0.8009130954742432","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":"Q452481$8BF99599-ADE8-4A5E-8CAD-B53C4C0E46CE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of partial satisfaction. II.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_partial_satisfaction._II."}}}}}