{"entities":{"Q799370":{"pageid":801218,"ns":120,"title":"Item:Q799370","lastrevid":48747232,"modified":"2026-01-05T18:47:03Z","type":"item","id":"Q799370","labels":{"en":{"language":"en","value":"``NP\\(=\\)P?'' and restricted partitions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3874612"}},"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":"Q799370$692186EB-3914-467E-B72B-25F222561379","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"89ca8a83a9cee15514bf0e897cc31174d6e9661a","datavalue":{"value":{"text":"``NP\\(=\\)P?'' and restricted partitions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q799370$3CB6F05D-C653-4776-9519-CDFFD6810AA4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78c02d71f326edd2e0ae064a067ca367407af563","datavalue":{"value":"0548.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799370$ACE766ED-A30B-478A-99D0-BC496C748F92","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"593c4b9902782b2f343829dacfcd6f2d0fde46d9","datavalue":{"value":"10.1016/0020-0255(84)90036-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799370$595C1FB3-47AC-4245-B280-2CB8D957D072","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c5832f8876614de1887b6fff71a1066143db327e","datavalue":{"value":{"entity-type":"item","numeric-id":786129,"id":"Q786129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799370$9C824B58-44A7-491F-A81B-6ACE25CBD852","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799370$2F73882F-C8C4-4254-BC19-5B2C39DD0AC3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q799370$C5CB1059-0BA3-4E4C-9715-B2B3A10D0AE1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7e725840494e1914c8c900fd5472db6339e2f3f6","datavalue":{"value":"Let \\(A=\\{a_ 1,a_ 2,...,a_ p,...\\}\\) be a set of natural numbers and s a given integer. If n can be expressed by  \\[  (1)\\quad n=x_ 1a_ 1+x_ 2a_ 2+...+x_ pa_ p+...,  \\]  where \\(x_ 1,x_ 2,...,x_ p,...\\) are nonnegative integers satisfying  \\[  (2)\\quad s=x_ 1+x_ 2+...+x_ p+...,  \\]  then the expression (1) with restriction (2) is called an s-restricted partition of n about A. The number of s-restricted partitions of n about A is denoted by R(n,A,s). This paper establishes a relationship between partition theory and the tractability of NP-complete problems. In fact, we have proved the following Theorem. If there exists a series of sets \\(A_ n=\\{P_{1n},P_{2n},...,P_{nn}\\}\\) with \\(P_{in}\\leq n^ s\\) for \\(i=1,2,...,n, n=1,2,3,...,\\) such that \\(R(\\sum^{n}_{i=1}P_{in},A_ n,n)\\leq n^ k\\), \\(n=1,2,3,...,\\) where k and s are constants independent of n, then \\(NP=P\\). In validating the conclusion we propose a dynamic programming algorithm, with a set of natural numbers as its parameters, whose time complexity depends on the restricted partition property of this set.","type":"string"},"datatype":"string"},"type":"statement","id":"Q799370$737E4BD7-EA47-4DA2-9417-C1728B5BD9F4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799370$2E8A5E12-8E35-485D-88B7-278823E03D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799370$1E7DC077-3856-4758-8A19-07E652E27C5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58d33fcd5e5cb8a52812aa5e4a2f3f30b5cf0e30","datavalue":{"value":"05A17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799370$5269BBB4-3EC2-4CB2-805D-03C9EF198937","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0501848942334a15c79b8772d697f89d8c9fbe53","datavalue":{"value":"3874612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799370$F6D4AECF-1B9F-42A5-B82D-055D32B78D6E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q799370$DF70BFC4-C8FC-4925-BF46-647CB6F1D011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65877a33cc32f28d9299834ec7531bb25d2bb898","datavalue":{"value":"restricted partitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q799370$419DA3AC-E290-4F49-A3C5-745B30F2ACC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c4e6f5ee3eb96ede7e096aad916387ba8743a62","datavalue":{"value":"dynamic programming algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q799370$968112EE-1F8D-428C-B6B5-7A37183795BF","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":"Q799370$A88B053D-A5F0-474F-929C-71C28D90DBA2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"254fa2f602b696ce49ebe2eaa3450999b0e374ec","datavalue":{"value":"https://doi.org/10.1016/0020-0255(84)90036-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q799370$9BFF8377-5B30-4494-9E92-D82C2D45975D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"957ec042b736a0d7206335403194da1e71e35684","datavalue":{"value":"W2052273480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q799370$03C6774F-4103-4E86-8E1B-3339D58B805C","rank":"normal"}],"P223":[{"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":"Q799370$F4F1FF6C-CA06-489B-8CB1-E9919A6CEA11","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":"Q799370$EFA6FC27-AA91-4CFC-909B-53C5684DB01D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dd20d30c3c1e5e0411ac04898dd85db19d616b8","datavalue":{"value":{"entity-type":"item","numeric-id":3900044,"id":"Q3900044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799370$862D4E51-CC81-43B2-B906-7DF6EDC381D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2af610cb9712f792a50bfe7cf87e5c3fca789b88","datavalue":{"value":{"entity-type":"item","numeric-id":4146776,"id":"Q4146776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799370$89A8CAEA-8BA9-46EA-9E77-D11FAD7941D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2f3c84fedec6be5b8f59fef93a6a8632cda3e40","datavalue":{"value":{"entity-type":"item","numeric-id":4101884,"id":"Q4101884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799370$F12A96E9-8FF8-4D6B-9048-9550908F0D03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f5f97cc67b6feb2628007ba354c2488ec91c5dd","datavalue":{"value":{"entity-type":"item","numeric-id":2652510,"id":"Q2652510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799370$EC4B3F69-3FBB-4DC1-BC70-907B8C56C828","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7544f31fbd77eb7f295e5d59ef5f17c9409aadfc","datavalue":{"value":{"entity-type":"item","numeric-id":1238704,"id":"Q1238704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q799370$281844D6-74E5-43F1-AD2E-5843699C56E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed282e01a9018fe3b8d9d929dba150cadc7388da","datavalue":{"value":{"entity-type":"item","numeric-id":1386936,"id":"Q1386936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"652a71ed27230ead4a359357774d784f12a1bafd","datavalue":{"value":{"amount":"+0.7849903106689453","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":"Q799370$EC23443F-09AF-49E5-8CFB-CD7E6D38649D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b9a7f8c26cd73b084ccdca63eab158f98eb3d99","datavalue":{"value":{"entity-type":"item","numeric-id":3799820,"id":"Q3799820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1550401787029b6172bf5d3e92c05411bfa8ded8","datavalue":{"value":{"amount":"+0.7573692202568054","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":"Q799370$F8AB2E4B-C4E3-4940-871A-11F9F292C7AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c72ece0a4bf02d731954761fb3ff36f90ac8ad04","datavalue":{"value":{"entity-type":"item","numeric-id":389094,"id":"Q389094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"298cda8b9c139df4cc5a53c09e5e3f6c738e5990","datavalue":{"value":{"amount":"+0.7551112174987793","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":"Q799370$3D1F1136-B37E-47DF-9689-DD8200AA0CC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1e6508c93b42e5f14e0682882c6e5c56af5b98b","datavalue":{"value":{"entity-type":"item","numeric-id":3161287,"id":"Q3161287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d54c3638b816cf9149190f51c1c1764ad63498fd","datavalue":{"value":{"amount":"+0.7548814415931702","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":"Q799370$420D5201-1F96-4CFE-8FBC-0832C5C7C711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1459ec4b3e6d5a1156e80a453578f8c6f3aa858","datavalue":{"value":{"entity-type":"item","numeric-id":3751375,"id":"Q3751375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f15dfe40e7a443bf9455bbf4ca5c8fbf8cc46ef0","datavalue":{"value":{"amount":"+0.7545890212059021","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":"Q799370$20B09CB6-8AB7-4177-A952-E654061ABF61","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:799370","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:799370"}}}}}