{"entities":{"Q1338895":{"pageid":1349634,"ns":120,"title":"Item:Q1338895","lastrevid":68500590,"modified":"2026-04-13T00:07:44Z","type":"item","id":"Q1338895","labels":{"en":{"language":"en","value":"On problems with short certificates"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 695003"}},"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":"Q1338895$1424E9ED-DE82-49C3-8446-019C8AB99588","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e5a2a16fcb4a82699f1196aa2bb67b9ab7171b4","datavalue":{"value":{"text":"On problems with short certificates","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1338895$B996EBE1-77B8-4328-99AA-4ECA9D99B33A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"55c39f89f6ab249030eb5c55bc75c9c91f6e9d28","datavalue":{"value":"0818.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338895$42D8FA09-D790-4595-80A3-A4A240B23BE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"957f74011ed7ebb8f7a9fab1f79ee93db590fce5","datavalue":{"value":"10.1007/BF01178668","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338895$1889F215-F7C7-498D-89D8-7AC7C8058B68","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$16B864B4-E29C-48E1-99CA-8F849E948F9B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ee1944e31358dfffdefe3a33d6a27ef17d9916b4","datavalue":{"value":{"time":"+1995-08-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1338895$A95B194B-1A5B-4B80-8FA7-A62DD7B102CC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c946a2a33763d495120c08cb1a2f6b5bb4ceef0c","datavalue":{"value":"We consider languages in NP whose certificate size is bounded by a fixed, slowly growing function (say \\(f(n))\\) of the input size. The classes \\(f(n)\\)-NP, which are related to classes of Kintala and Fischer, are defined in order to classify such languages. We show that several natural problems, involving Boolean satisfiability, graph colouring and Hamiltonian circuits, are complete for \\(f(n)\\)-NP. Each of our problems is obtained by taking a known NP-complete problem and introducing an ingredient we call forcing, whereby a partial structure is enlarged by a sequence of local improvements. As special cases of these results we obtain some new logspace completeness results for P.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338895$CA14CDD8-FADB-46DF-B3EE-83BB51D1210E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338895$EB5FFE10-D991-462C-AD0F-75D62A88A3AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338895$94B195B4-3825-483A-B1DE-72FC6388D6F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338895$7C7EBDD2-ABD7-42CA-BC0A-B0DA6AC8F13D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5eb48f46d62df6e952ebd85ca61c300ebf7f9261","datavalue":{"value":"695003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338895$E9CBD0F0-97F8-478E-85E9-EED6AFBF699C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3978d2f31bc86b19c4025fe772ec1974bbd09669","datavalue":{"value":"Boolean satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338895$9E73F8B6-7A5C-44C0-9D4C-677EA5C0F62E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"def48283d510794913c58f78056b808e00633a5c","datavalue":{"value":"graph colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338895$E964D930-31F2-4A49-B480-446D3A429791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fe9da2c2189abacacef5c76c3c62ac70e81c61c","datavalue":{"value":"Hamiltonian circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338895$61BAAAEA-E6C2-4BC2-A0DA-4B95B41D0677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b23248042bd506455f51600d00d7ec5443276f9","datavalue":{"value":"forcing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338895$AF4B1DE8-D1D7-487D-A7AF-0983E6B10898","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c10b05f408b175fc9b864bccc0f940febdbc4691","datavalue":{"value":{"entity-type":"item","numeric-id":810039,"id":"Q810039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$3E5355A2-58CA-4666-9FF4-BB2A327E809A","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":"Q1338895$891277AB-8E4C-4229-AB29-65EC0D78122F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$7C78DD4D-EE53-40E4-83AA-1832BC4859B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0e6b90c16ae5fa1eac19212a306cb84ffec72b","datavalue":{"value":{"entity-type":"item","numeric-id":5613969,"id":"Q5613969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$5583C6FA-EF8D-47B9-AA16-A958CCBDCF23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ee0d8e4c28135414cd0564a619e491715231def","datavalue":{"value":{"entity-type":"item","numeric-id":3034815,"id":"Q3034815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$EA764C82-43C3-4228-A63C-2B055876A6CA","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":"Q1338895$AA53D347-541E-4CB3-AE31-14D16E506073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$72F7CC40-D8FE-428F-9685-EEC2FB7DE281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$268D33A1-AFCD-46A0-BD77-027221DBC9DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"373c65ef4069b52a23fe230e08a271e32f56a00a","datavalue":{"value":{"entity-type":"item","numeric-id":1235982,"id":"Q1235982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$7F75DE7F-2489-42EB-9574-76ECF6D3238F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65049120db84eb3a64559cb6dce6f2ce61c91d9a","datavalue":{"value":{"entity-type":"item","numeric-id":3893305,"id":"Q3893305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$2ECE176E-7428-4464-9B7B-81D674D4231B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$5DAA808C-1424-4191-8BCF-5EF8A436EBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30fc5d7c7ecaa299c8aecd66b67013caa8e29726","datavalue":{"value":{"entity-type":"item","numeric-id":3740256,"id":"Q3740256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$2EB7D73C-A6E7-4987-AECA-94C45783671A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1f0209c662a26c652a065cc280f3e4e1081f4d","datavalue":{"value":{"entity-type":"item","numeric-id":1822500,"id":"Q1822500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$350C731F-F7D6-42EC-9D7E-DDE40FAEAA50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$0C486421-DB7E-4326-AC0A-2AC834BD16E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338895$8AC090DD-DED7-4E5A-85ED-60E4A5097487","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c69ff1dc66785601f813e146416692e1f382666","datavalue":{"value":{"entity-type":"item","numeric-id":2014630,"id":"Q2014630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4bcdd41f3d19f031d5cf7138673a4139ae0fb2f","datavalue":{"value":{"amount":"+0.82542235","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$3BDEB659-832D-4A68-AD9B-242D0AABA8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f57b518d4aee2cb28102c1a202134036afa1f8f6","datavalue":{"value":{"entity-type":"item","numeric-id":5196806,"id":"Q5196806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5d75fee40dca8f1160820550f75e16f65f333ba","datavalue":{"value":{"amount":"+0.8195331","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$0AF9F90E-6897-4EF6-9F94-109A4C94751E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fd6ab87c8850e60d034736af869f3287be0411e","datavalue":{"value":{"entity-type":"item","numeric-id":1007845,"id":"Q1007845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0e4d787959fc07e5fc19acea81ba45c906f43f9","datavalue":{"value":{"amount":"+0.7943216","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$B255A1CE-73AC-43DC-80AF-781D5B3096DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5963eaaf3e356e73042afa5dd3f48623ba01864","datavalue":{"value":{"entity-type":"item","numeric-id":4434881,"id":"Q4434881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cabaf7705efaba5635b2ad005ce437e110fc5717","datavalue":{"value":{"amount":"+0.7856833","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$4B802A85-7B56-491E-A4C8-C4A50C790B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79a4e70c967ac3bff8c9fa1dd5f7a3fad454b70b","datavalue":{"value":{"entity-type":"item","numeric-id":5502752,"id":"Q5502752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28fa79b8e820a67923a7da9986a337d4f6c839a1","datavalue":{"value":{"amount":"+0.7827904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$35384A58-BF7D-4781-8325-9D3CFD204200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a87ec75df59051d3acf7f5eb71147802c7d2708","datavalue":{"value":{"entity-type":"item","numeric-id":636560,"id":"Q636560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2df890d56cea06f5989c2fbd5a16322daba8564","datavalue":{"value":{"amount":"+0.7761791","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$E738BE66-AF52-4EB2-AFD3-4A1ADA56D9CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"364d86e538ea96f4de5c3b6e3a6ad50b67e3ca9d","datavalue":{"value":{"entity-type":"item","numeric-id":3102214,"id":"Q3102214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bc9944b6769bc561e0456b80a5912954b78474b","datavalue":{"value":{"amount":"+0.77286357","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$F2F885D3-3C2D-4EE8-BC76-E2334A10613F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41b93d75139905400c985baf8983e41b98aaead6","datavalue":{"value":{"entity-type":"item","numeric-id":1378501,"id":"Q1378501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5af255e8fef9aedd5da22096de5dc8c59eb6c755","datavalue":{"value":{"amount":"+0.76871485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$AA7C7FF8-9E49-47BB-8242-485CE4B87301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a29597aaf313a8e7a91f98803c2d97eebbb60a49","datavalue":{"value":{"entity-type":"item","numeric-id":4448398,"id":"Q4448398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2231fcc3d5f0170fa1abd6fe800c1b312dc67ede","datavalue":{"value":{"amount":"+0.76838136","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338895$26A5F322-0658-4602-B56C-6D2EBBF7CE11","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On problems with short certificates","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_problems_with_short_certificates"}}}}}