{"entities":{"Q2479500":{"pageid":2490243,"ns":120,"title":"Item:Q2479500","lastrevid":73337121,"modified":"2026-04-14T15:29:14Z","type":"item","id":"Q2479500","labels":{"en":{"language":"en","value":"Permuted max-algebraic eigenvector problem is \\(NP\\)-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5254216"}},"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":"Q2479500$682D7AEA-AEE2-4C4D-8716-11A1BA5D5031","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"443f41190e255bf4dd72487aa0c6f0e0449adb05","datavalue":{"value":{"text":"Permuted max-algebraic eigenvector problem is \\(NP\\)-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2479500$1848A50B-4863-412B-A39D-46D2E0659147","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5a811fc29faf1bea96d566b958c92f8a445fc6b8","datavalue":{"value":"1149.65024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479500$D8845E84-D8C8-41FB-876A-CFB863CCA3E2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$0142EAC8-A859-426B-BB75-53E93554B112","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5e0cdb440ca46d9b8c69635fc01191f2bcf2170","datavalue":{"value":{"time":"+2008-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2479500$CDA9AAD0-5DC8-4F0A-8BD1-C64E63C6C482","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f8043957313ce3813bd82ea1a3f216e61ae3e1f","datavalue":{"value":"The aim of the paper is to prove the NP-completeness of the following permuted eigenvector problem: ``Given \\(A\\in\\overline{\\mathbb R}^{n\\times n}\\) and \\(x\\in\\overline{\\mathbb R}^n,\\) (\\(\\overline{\\mathbb R}=\\mathbb R\\cup{-\\infty}\\)), it is possible to permute the components of \\(x\\) so that it becomes a (max-algebraic) eigenvector of \\(A\\)?''   The first section is an introduction in nature.  The second section focuses on the \\(NP\\)-completeness. The author proves that the integer permuted eigenvector problem: ``Given \\(A\\in\\mathbb{Z}^{n\\times n}\\) and \\(x\\in\\mathbb{Z}^n,\\) is there a \\(\\pi\\in P_n\\) (the set of permutations of the set \\({1,2,\\dots,n}),\\) such that \\(x(\\pi)\\) is an eigenvector of \\(A\\)?'' is NP-complete for the class of normalised, strongly regular matrices and the NP-completeness for all integer matrices then immediately follows.   The conclusions are presented in the third section.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479500$5C092357-996B-43EC-92D5-F924FC764AB2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1fd405649af5a3f9a37557a0bd816920cbf1d33b","datavalue":{"value":"65F15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479500$5B92F9C7-FEAF-4812-A804-5FB39AC1868B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479500$D262675D-1F87-42F7-A6B0-E7EF64157024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479500$1A5B577F-CBA7-4327-8C93-E6D35C254F03","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"62fba65a6cc6050e94f28547e10a533b17f5aa9a","datavalue":{"value":"5254216","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479500$99BCF33D-C063-477B-9893-AF1A2A45A1CF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdcc858e642c37f46f6fa377f2e2634fe466a35","datavalue":{"value":"permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479500$5EACBA86-FDCB-4583-8516-9D05C71894FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479500$20F7BD79-E8CA-493B-A530-A05CEFE54F0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb4dc8abdba0736491075f2c2c442578e0fa9536","datavalue":{"value":"eigenvector","type":"string"},"datatype":"string"},"type":"statement","id":"Q2479500$94328AD3-BEFC-458E-B791-3B1C6C673790","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef7f9b00e70cc9184062d1b22183cdd374cca76e","datavalue":{"value":{"entity-type":"item","numeric-id":217085,"id":"Q217085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$B0140B48-AB9E-4D2C-B901-E6B03C4CFA30","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f1c17458e07d412518a49e985e3e753c6b8e4ec7","datavalue":{"value":{"entity-type":"item","numeric-id":175020,"id":"Q175020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$61EC4D13-5DAF-4071-96FA-58D7602F08E0","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":"Q2479500$9EEA96CE-BC55-46A0-AF0B-C57842EE65CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b78e714670b2c0c71aad93cd429affe14ccc5580","datavalue":{"value":"https://doi.org/10.1016/j.laa.2007.10.032","type":"string"},"datatype":"url"},"type":"statement","id":"Q2479500$6E1CBECB-F44C-4178-BC57-8B532EBECE3D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"21f36d738eb1326c315fd680e90f2dee2672d4ae","datavalue":{"value":"W2038320624","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479500$84A362BA-E19E-4F9B-9CE6-F8E21573AE16","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f249580a521efbf8ec95a14e96ab42705350cf25","datavalue":{"value":{"entity-type":"item","numeric-id":4304869,"id":"Q4304869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$F33E5D25-F569-4A28-95F7-24AC1C7EEAEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8812919d16364b06f0837b92df69757657879240","datavalue":{"value":{"entity-type":"item","numeric-id":1582069,"id":"Q1582069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$72CC1B2A-A7C7-4D4E-A069-DDEB6D6C8827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d52103bd8c04debb8cb34cd507cde9e882726dcb","datavalue":{"value":{"entity-type":"item","numeric-id":1873718,"id":"Q1873718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$8236DC97-6141-4EB5-B637-BACCB24D1C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ce1b78a9a65a9e5aa5d1107722dc82109408fa","datavalue":{"value":{"entity-type":"item","numeric-id":1082274,"id":"Q1082274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$B6976447-EA0F-4CF5-8317-888AAC7BEE4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61e681096f1af7d2aeb13d0ef4f7c1b0c466cc50","datavalue":{"value":{"entity-type":"item","numeric-id":869906,"id":"Q869906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$60B5BFE0-3785-4CA4-A330-14DFDB9CEF03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcbd2c15e3dc6779d9e230f45f2f4800bd9d2447","datavalue":{"value":{"entity-type":"item","numeric-id":3584166,"id":"Q3584166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$9A4B1DF6-4542-47CE-AB7F-794E6A8F123A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0d2aad65a6ed74c1caecf463ff11e678991de2c","datavalue":{"value":{"entity-type":"item","numeric-id":3221803,"id":"Q3221803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$A1121516-F9BF-4B32-9867-9691C3A7E56F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a339108f845f381ae162edfeda7b58a976de693","datavalue":{"value":{"entity-type":"item","numeric-id":1254944,"id":"Q1254944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$F575B56C-11AE-4ED0-B392-9B4F24E01E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f16e239943b6a37fe536192e9fabcab0b3d3308c","datavalue":{"value":{"entity-type":"item","numeric-id":1175739,"id":"Q1175739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$1182DEA3-3E4D-443B-B801-9B10B8E3E26A","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":"Q2479500$D931E3C2-6ACC-48E2-A545-27D3CF2E8AA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87275d8f3e3ee98146b4e4dd034a7f8953926332","datavalue":{"value":{"entity-type":"item","numeric-id":5200628,"id":"Q5200628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$11568871-0556-40BD-8033-C3E13CFF2C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f970782cef7606d75b439e57c5964589154083b2","datavalue":{"value":{"entity-type":"item","numeric-id":1249587,"id":"Q1249587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$1D8E28D8-96A0-403F-8802-E6F20091CE04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fd8a41e9da3e8e7dce76b60e6d7e73f605f702a","datavalue":{"value":{"entity-type":"item","numeric-id":3594377,"id":"Q3594377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$E3731F9B-9B33-46A1-9C1B-D96362C70FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77fd56549136e337ad67107d48f2d866cfa772f2","datavalue":{"value":{"entity-type":"item","numeric-id":5290261,"id":"Q5290261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2479500$A1E10701-DB56-4F5C-935E-AD14BF065FF3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c7c5a1eb26e981105cf7ec7ca6690ff7306db9b6","datavalue":{"value":"10.1016/J.LAA.2007.10.032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2479500$F582E14E-B8A2-4536-ACF1-317A1118ECCF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"496f103df3fae20154b4d20fb88627f16bd75a92","datavalue":{"value":{"entity-type":"item","numeric-id":4521209,"id":"Q4521209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e267570cb6ead8f6de4de906c8fc0c7fe18f634","datavalue":{"value":{"amount":"+0.7835392355918884","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":"Q2479500$7C2A3203-6716-43B3-A10F-AC00D32B4F8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227179b3927c996d4053d5b7b90cc78f9e2e3591","datavalue":{"value":{"entity-type":"item","numeric-id":2474561,"id":"Q2474561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e267570cb6ead8f6de4de906c8fc0c7fe18f634","datavalue":{"value":{"amount":"+0.7835392355918884","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":"Q2479500$58B9A11C-9806-4461-8FB6-8B26D0CF1915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e7b0c46548642362b0586eaac32f12e160ffae9","datavalue":{"value":{"entity-type":"item","numeric-id":4509104,"id":"Q4509104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"479fee26c04e66cd34b5e88591f70d87fae5d46a","datavalue":{"value":{"amount":"+0.7578103542327881","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":"Q2479500$64175107-FDB1-4EBC-BB29-F99F2D44B1EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cbaf7ed17a3042e817fb336f6737f02c7b5f1ce","datavalue":{"value":{"entity-type":"item","numeric-id":4764873,"id":"Q4764873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"479fee26c04e66cd34b5e88591f70d87fae5d46a","datavalue":{"value":{"amount":"+0.7578103542327881","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":"Q2479500$15D3A76C-94C3-42B9-9C90-C1C0061A9EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5970cdf1bf79478efa23667be15a1dd2b2ab783a","datavalue":{"value":{"entity-type":"item","numeric-id":516821,"id":"Q516821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92aba239b24d85e9ed4dd3e50f336a1267040a86","datavalue":{"value":{"amount":"+0.7442964315414429","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":"Q2479500$67255C6A-6506-4A9B-943C-30A0D91CBD03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Permuted max-algebraic eigenvector problem is \\(NP\\)-complete","badges":[]}}}}}