{"entities":{"Q1098635":{"pageid":1109387,"ns":120,"title":"Item:Q1098635","lastrevid":66127221,"modified":"2026-04-12T07:43:50Z","type":"item","id":"Q1098635","labels":{"en":{"language":"en","value":"Nonconstructive advances in polynomial-time complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4039296"}},"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":"Q1098635$D1F7972E-E20C-47BB-B212-97A2E089C8A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4f62b31bb268989aa24d753acb9e4b468c3c4689","datavalue":{"value":{"text":"Nonconstructive advances in polynomial-time complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098635$201B7755-70E4-426B-8B7D-911C74AED0E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f65bc8e994c62092cfbf8b7a2a615145c3165ed1","datavalue":{"value":"0637.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098635$54F5E347-1A71-4943-907B-E641984DF114","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd63f91c11e0957cf4cbf1ea899a454b8a72aeeb","datavalue":{"value":"10.1016/0020-0190(87)90054-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098635$2F6118D3-FE54-46C8-8060-8916414067EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"057c48278a1d014d58f7703e66b1dc164eccfbc4","datavalue":{"value":{"entity-type":"item","numeric-id":175527,"id":"Q175527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$066FE4C9-3C6B-45EA-9862-0B908BCA668E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d288423df0deba1f237a49670693efc500bb8d57","datavalue":{"value":{"entity-type":"item","numeric-id":293396,"id":"Q293396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$3A56B259-78A4-4467-A5CD-0C59F99DD338","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$895A60D7-3360-4C00-978C-53A8AACC73DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1098635$EFEFA087-EE61-4D08-9A47-B56D2877078A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"441a4542ced38cf4b0f9144984f917f74c06e4e1","datavalue":{"value":"The following decision problem is defined: Gate matrix layout (GML): Instance: A Boolean matrix M and an integer k; Question: Can we permute the columns of M such that if in each row we change to * every 0 lying between the row's leftmost and rightmost 1, then no column contains more than k 1's and *'s ?    The main result of the paper is that the fixed-k version of GML is solvable in polynomial time. The proof is nonconstructive and is based on a result of \\textit{N. Robertson} and \\textit{P. D. Seymour} [SIAM J. Algebraic Discrete Methods 6, 300-305 (1985; Zbl 0565.05045)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098635$3F660D67-D43F-4BA2-9CE0-F9085FCC259D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"67aeec512b636e4668aab1b914be3244788dfcae","datavalue":{"value":{"entity-type":"item","numeric-id":914549,"id":"Q914549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$15D1DC10-CC8A-466D-A022-9C0E22902F0B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098635$21DADA2A-7673-430A-85BD-FC320949B78D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098635$2C46FE5F-F92F-4B84-B7C1-343F6594104C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ebe39fb30930c789e9c652d011e47b67458ff5cd","datavalue":{"value":"4039296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098635$BCC33610-162D-43D2-BB33-A41C2DC75197","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c83af40cf6d9db89662353da4f7d97e4a75d8ed","datavalue":{"value":"Gate matrix layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098635$87DCBA1B-34A8-4E96-8BBE-499EEFE784F1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"08b29f2632ae425847a7ac8f0e66ab621cf4e84a","datavalue":{"value":"Q57360197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098635$4AE08268-0A65-4095-8613-BF0AD905E51E","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":"Q1098635$F977C63D-6438-4BDB-A471-2796496C8A1F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fdeba845fff285420a05ef92a4965df244493b2f","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90054-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1098635$08FFFA5B-EBEC-4783-99A4-4A1BD2F2DFB0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1398dd713daec48960e516963aa2cb6e61c7678a","datavalue":{"value":"W2000611521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098635$D444D699-7F18-4DA6-8558-7F93E2D7647C","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":"Q1098635$26374606-5BA5-4F48-A840-94D66CDCA0FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9d5b23b5f6cd07dffa9f9ed4247b217c1931468","datavalue":{"value":{"entity-type":"item","numeric-id":3679228,"id":"Q3679228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$996D4C80-DA4E-49EA-B597-EE01214BDB89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bac9e96668c7ec0f829bbe6125b2c6a54e606e8","datavalue":{"value":{"entity-type":"item","numeric-id":3684139,"id":"Q3684139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$9F235F0B-6A39-4E2A-A9C9-B23669C87D4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5376391ab6b394f7893094fcbfc13d81f395664f","datavalue":{"value":{"entity-type":"item","numeric-id":1068821,"id":"Q1068821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$B2C3D568-4ABE-4956-8388-E1C94C29DE7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20b852a7a28bbec3b861b12cebdf1e5b87806fca","datavalue":{"value":{"entity-type":"item","numeric-id":2645755,"id":"Q2645755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$266951CC-4393-4E8A-B5DF-37FA426E1322","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"863a7eccc7499ec0dad2fcd355a698a3a2f419a1","datavalue":{"value":{"entity-type":"item","numeric-id":3798236,"id":"Q3798236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098635$A574ED94-B710-415C-91B1-3F0777771569","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"f1f2fd9f6f053406aaf9cdabbd91e5d9bcff1552","datavalue":{"value":"journals/ipl/FellowsL87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098635$0EA29E9B-94E0-4477-BED2-0F1913F15B66","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6be7fe92cfffd58c37a6d48c371420c2aa4e5e67","datavalue":{"value":{"entity-type":"item","numeric-id":3798236,"id":"Q3798236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f319977d2879c612e73e4ec56529491cddea2cf7","datavalue":{"value":{"amount":"+0.7550130486488342","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":"Q1098635$4E438B4B-BEC8-4D7D-875E-D0D0F6F070FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cd60c6d65556c4ada1cd2b9fe12ddb2f8deb85b","datavalue":{"value":{"entity-type":"item","numeric-id":5959101,"id":"Q5959101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d18dc4d3e1d62895b8f2564e1d7eb25bc06acb1","datavalue":{"value":{"amount":"+0.7547109127044678","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":"Q1098635$C8AF62B2-F8DD-4CB9-810D-8C40D863D610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1075d6b1dc0bbe847b2626c17dbef386cfb2cbb","datavalue":{"value":{"entity-type":"item","numeric-id":1182305,"id":"Q1182305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a614108f8debf571093406b4f5f153c45509aa9f","datavalue":{"value":{"amount":"+0.7225117683410645","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":"Q1098635$63ECB141-5252-46A2-A32D-6DAA19CD573B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99fe66c737cc9efdf17c59288792f81e071959ef","datavalue":{"value":{"entity-type":"item","numeric-id":1393029,"id":"Q1393029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"264f9949118dc0f6acd34d9d135b347429e05af7","datavalue":{"value":{"amount":"+0.7057349681854248","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":"Q1098635$B74A1D41-26C2-4B8B-B485-F6193D45CA59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9db214181cabc7a91da703e9dea4fd0696b16c37","datavalue":{"value":{"entity-type":"item","numeric-id":4820785,"id":"Q4820785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9d57e655f079fcf88bdd3b31f8c2eb23ac602e8","datavalue":{"value":{"amount":"+0.70573490858078","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":"Q1098635$ADCD6121-FF08-4C6D-AE28-89A8CE1FE662","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonconstructive advances in polynomial-time complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonconstructive_advances_in_polynomial-time_complexity"}}}}}