{"entities":{"Q1091815":{"pageid":1102567,"ns":120,"title":"Item:Q1091815","lastrevid":49081576,"modified":"2026-01-06T13:54:44Z","type":"item","id":"Q1091815","labels":{"en":{"language":"en","value":"Average polynomial time complexity of some NP-complete problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4011930"}},"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":"Q1091815$02FE1716-C535-4CDF-971D-9A7FDCAD1BE2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d169eb4b3911427aa02d424a195e8b5754c12ced","datavalue":{"value":{"text":"Average polynomial time complexity of some NP-complete problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1091815$519CFA23-A603-4500-8FE8-E79918AA759D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"516fa7a67ec1cf0a26884eb33104644823325faa","datavalue":{"value":"0623.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091815$6A193FB0-94F0-49F8-85AE-E3135139B49D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8bc2a1f568feb052345e7f21df17ae45a8d2074a","datavalue":{"value":"10.1016/0304-3975(86)90031-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091815$C4ECE51B-D3BF-4720-BB9E-EACD7DFA5794","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"23334c6c9bd3a471149caf760dede1de6d0c7631","datavalue":{"value":{"entity-type":"item","numeric-id":1091814,"id":"Q1091814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$A47FDB95-C700-4CFA-8BE0-A67531156A01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2817c8aa49bac291785aeb3d22b538d01e8574a7","datavalue":{"value":{"entity-type":"item","numeric-id":712284,"id":"Q712284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$686401AC-ACCB-401F-9792-CB9C41BBD6FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"89422ad86a075deddfffc02ee2500b3e6fbefe01","datavalue":{"value":{"entity-type":"item","numeric-id":210617,"id":"Q210617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$00BCB8D4-3823-4167-8C7C-D4662446DEFA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$F5EEA5FF-4AB7-44C6-A22A-635C56707D1D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1091815$F95F17F5-2671-4376-B6ED-328B6B8A9B35","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6a2b56ab3f6f3195fd2a3180843555825f32b03c","datavalue":{"value":"Random graphs with n vertices are considered such that any edge occurs independently swith the same probability p. It is proved that the CLIQUE problem can be solved in average polynomial time for these graphs when \\(p=n^{-\\epsilon}\\), where \\(\\epsilon >0\\) is a constant. Besides, the problem CLIQUE(N(n)) is considered for the graphs with a number of edges less than N(n). It is shown that this problem can also be solved in average polynomial time for any function \\(0\\leq N(n)\\leq n^{2-\\epsilon}\\), where \\(0<\\epsilon <2\\). Provided that \\(N(n)\\geq n^{\\epsilon}\\), the latter problem is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091815$8D961AED-F22D-4CFC-9293-65E54D131A69","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091815$00336093-F218-4477-B042-F9D6FAA7B2DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091815$59019EFB-960F-4303-A4E5-72E427BB07BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091815$5A503FE5-97FC-4F27-95AB-64A5AC09538A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bbc1b7b44d8113e0c1aec024c863a7cae18f26fa","datavalue":{"value":"4011930","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091815$546554EF-CEF7-43E3-8CD7-12BDEFFC233D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50dc5a1d041f9e444212e60e5236dde69d229f7d","datavalue":{"value":"NP-complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091815$12C66034-7B9F-4A71-9DCB-9AA316FF19EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"474ff8cf83435906613664409cf0e46e352f9262","datavalue":{"value":"Random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091815$3140246E-556A-4D66-816E-684A0DBDCFFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b6d7fc79c7172c20189a84d73f93acf5eac931f","datavalue":{"value":"CLIQUE problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091815$93A03765-3E61-4C0A-AE0B-6B753F09236D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec2bb996184cb972dc732f490a3cffe3f3b0dd0b","datavalue":{"value":"average polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091815$890CA30B-BB63-43E6-BE20-A36414AFBA54","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":"Q1091815$F9308BC5-3A46-45D8-B12E-F3BC57375C75","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f0f375cd536947a12c22d012fd843f407fdc8f79","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90031-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1091815$40FD8327-B57B-4B93-ACEF-09DA7F879928","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"98776f454588f2ae4b9f9e06e8fc1c4e07b19024","datavalue":{"value":"W2062731608","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091815$36E13C90-EE50-4B03-B068-4570ED2BEE8E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$8331B631-F408-4922-BA3B-E354D295A623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba5c523b785f3698ee48d79f73aee094f52b7c15","datavalue":{"value":{"entity-type":"item","numeric-id":3951539,"id":"Q3951539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$1267C31A-17C3-49C6-8E7F-658707A30324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$AD9EEE5B-682D-48B3-A21E-A771B7E0ADDF","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":"Q1091815$2136C8EB-BBB9-4B3C-B1D8-FCE2A9DDF864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6254e3774534a53de166055c12cccf75cb257bc2","datavalue":{"value":{"entity-type":"item","numeric-id":4050627,"id":"Q4050627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$1A7C2F2F-D1EE-433A-9E56-3F368DF29B4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"295a70c178855625d44b3d929ce0d3758a1bb37f","datavalue":{"value":{"entity-type":"item","numeric-id":4144785,"id":"Q4144785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$529D0D6E-CA8F-4EA7-B6D2-F5AB004903D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78d90dcfae0ee3a6aab4fd059af90abf8af2354f","datavalue":{"value":{"entity-type":"item","numeric-id":3668868,"id":"Q3668868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$C984DD61-A1C7-49AE-BA46-F3DEB7DA6321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e62f30e5631357c3f5e5f8bb81223096e4c337f2","datavalue":{"value":{"entity-type":"item","numeric-id":4141146,"id":"Q4141146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$10A2F195-0A7D-4154-B866-F8EBB8E844E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"652994a4fb48ee4d98f04d114f2dbf6a5c2d14b4","datavalue":{"value":{"entity-type":"item","numeric-id":1147713,"id":"Q1147713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$D714185A-0E2F-41F6-931C-2CD8CBD12F9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f238224e19e547aba54d67f39705cf590b4d21c2","datavalue":{"value":{"entity-type":"item","numeric-id":4063075,"id":"Q4063075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$6F4523A9-4B64-4B3D-AA55-3F06F75DDE47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f7f462eb64db37210f42380ef8802fd3e1cf3b8","datavalue":{"value":{"entity-type":"item","numeric-id":4159413,"id":"Q4159413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$A8CDAE40-65DD-48FB-B054-E23EB75D8F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90ce379660257488dec544d9ec7f9d6ae3da2a84","datavalue":{"value":{"entity-type":"item","numeric-id":3885209,"id":"Q3885209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$02AE610C-E449-405C-92B0-DEFA15ACA499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8004eae2ffc5a942ba5a6e8374f263f0fbb9e96","datavalue":{"value":{"entity-type":"item","numeric-id":3912012,"id":"Q3912012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$91C0FB93-26E4-4634-920F-9C44F92ED984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0387d62c6ee650f059930e6c57169d1a38adeac8","datavalue":{"value":{"entity-type":"item","numeric-id":3040925,"id":"Q3040925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$C6820379-A54B-410D-90A6-4B52A0A0C165","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dc8a1faedec1647ff5e9aefae185cf306f2bc5","datavalue":{"value":{"entity-type":"item","numeric-id":4133117,"id":"Q4133117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$8D6DA6FE-8DBE-4E3C-8022-7E318E51ABB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb85e2a08b123210f7ea1cf8a8c1c958121dd184","datavalue":{"value":{"entity-type":"item","numeric-id":4138754,"id":"Q4138754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091815$8523E9FF-0A62-4BFC-99EE-E20C4BB88FD8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4b306dd9dc3fd5f97aed5fb146d9df7974d553c","datavalue":{"value":{"entity-type":"item","numeric-id":6487965,"id":"Q6487965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37a2c413d62bf742c37c40c24f29ff7ff9ccd624","datavalue":{"value":{"amount":"+0.8260840177536011","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":"Q1091815$B748BB3D-E9CB-4948-97C1-0B9019DBB0FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1894525fe698a79941af30981e885df202eb079d","datavalue":{"value":{"entity-type":"item","numeric-id":3031922,"id":"Q3031922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3774439d0e5ae343bb18e01741443de9a03b67b8","datavalue":{"value":{"amount":"+0.8189444541931152","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":"Q1091815$0CBCB7B0-D8EE-46A8-ACBA-C348D922F662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5918034b188190827aa4c98082ddb9211d653ab8","datavalue":{"value":{"entity-type":"item","numeric-id":5419039,"id":"Q5419039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e25ca00e399569a7a0b76d9e3167d57d44279c47","datavalue":{"value":{"amount":"+0.7823053002357483","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":"Q1091815$AD7D7B0C-E774-49C8-B573-FC4E509F4B9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a3cfcf4d569da1629869828a52c315605971a2d","datavalue":{"value":{"entity-type":"item","numeric-id":4962593,"id":"Q4962593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"660fa1ba026117a4b1f9d38e67238f4ac0ea818b","datavalue":{"value":{"amount":"+0.7768943905830383","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":"Q1091815$E9069FFD-4C9D-4745-A954-A0479C41E1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3cfd1218842df444f57110490d5b55338697e5d","datavalue":{"value":{"entity-type":"item","numeric-id":2344729,"id":"Q2344729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87ed874c7596e2624f03cf82a2d5c0bc12e3830f","datavalue":{"value":{"amount":"+0.775200366973877","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":"Q1091815$E352849B-64EA-4E9C-96E1-A0A3786E9123","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1091815","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1091815"}}}}}