{"entities":{"Q377802":{"pageid":379569,"ns":120,"title":"Item:Q377802","lastrevid":61381386,"modified":"2026-04-10T23:00:00Z","type":"item","id":"Q377802","labels":{"en":{"language":"en","value":"Disproof of the neighborhood conjecture with implications to SAT"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6223883"}},"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":"Q377802$C7DF5FDC-4381-441D-B7CC-662EBF9DF775","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a5ad74080f5e96093142fc7d691a3e83fc35dafb","datavalue":{"value":{"text":"Disproof of the neighborhood conjecture with implications to SAT","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q377802$448804B7-670B-4D11-A095-B18CD6A8D457","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"77c9de469612c92af97ef6aca6ebf87cfa1fa900","datavalue":{"value":"1289.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$2A402ACA-7E45-4A08-83E3-C0EE619C6948","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f882b74bf32f34e15d83ed334c2173fb9313dd1","datavalue":{"value":{"entity-type":"item","numeric-id":377801,"id":"Q377801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$96E045C3-1163-47B9-8238-E353B975F017","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$AE2213C3-9F84-4280-A3DD-49DE1F3ECC40","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"441bbdae4ae4e2c8e7b771fabeb4058d99f8f1c2","datavalue":{"value":{"time":"+2013-11-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q377802$766AF867-74EC-459C-B581-D1727C1830A2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9415326c63199b870fda9f4ffab749ebccbf38f","datavalue":{"value":"http://hdl.handle.net/20.500.11850/61671","type":"string"},"datatype":"url"},"type":"statement","id":"Q377802$A22297A1-1904-48C3-8AC8-1096AC31ED19","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"100bfddd03ab3e78b7d60f62f090ecbf61b44de0","datavalue":{"value":"In a binary tree (a rooted tree whose nodes all have either 2 or 0 children) a leaf is \\(\\ell\\)-close to a node if the node is an ancestor distant at most \\(\\ell\\); a \\((k,d)\\)-tree is a binary tree in which every leaf has depth at least \\(k-1\\), and there are, for every node, at most \\(d\\) leaves which are \\((k-1)\\)-close.   Lemma 1.1: A \\(\\left(k,\\left\\lfloor \\frac{2^{k+2}}k\\right\\rfloor\\right)\\)-tree exists for every \\(k\\geq1\\).  The author advises in her introduction that this lemma ``will be the main ingredient in proving some new results on Maker/Breaker games and SAT'' (the ``Boolean satisfiability problem'').  See also the detailed abstract of the author's paper [Lect. Notes Comput. Sci. 5757, 764--775 (2009; Zbl 1256.68083)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q377802$8E770FCD-7D08-4B8B-9562-15B892AF3CF6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$EE84394C-6040-4D88-B90C-BBE2025D1DF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$83ADCD33-0DA5-46CC-9DF7-D4E286DC6C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$98D591C1-E6EF-4F0F-8C6B-FA2FE216A230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$046FF9C2-7434-4E0D-BB52-41F78290015F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$8FDD65C3-1714-4C39-B589-0007CD6E884A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$DA6270FD-5A5D-4F1A-9318-76D26982FD73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$A0BE3D94-C0DC-40E8-B071-2D27758B04DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fbd0918ba2c4a1aeddd30d9d3d146d9773f1239","datavalue":{"value":"91A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$51BE25C9-C948-4A17-9B96-5F69A7DD7EE8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f156064c805d6dbea7a3c973ca591551787c622","datavalue":{"value":"6223883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$AACE5CFD-BDDE-41A5-88C8-DA8FC2A09C48","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7bcb48c25db0908929ba2383247380f87f15321","datavalue":{"value":"binary tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q377802$033682BA-A2E4-4F54-B90A-98A9851F9A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5867ec7b44aefc01672736513dfe6410a0300cd5","datavalue":{"value":"SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q377802$A9A6D392-F429-40AC-91EC-DC3366E773D2","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":"Q377802$96E4986A-1F90-40EA-B1C5-5EF886D2C001","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6fbab2d6b459c335aeb531189e61b4c780c09c2a","datavalue":{"value":"W1782236248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$695EE195-9CB4-4BA6-8DE1-B0D8A5EFE0A5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d22001ae560c460a5b3a00c15e976f174085addf","datavalue":{"value":"Q123017151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$46F5C41A-57FD-440F-B6B9-EA8458694D51","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"725c84c2ebc6f4b154eb6d601e5b793715036a34","datavalue":{"value":{"entity-type":"item","numeric-id":1087560,"id":"Q1087560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$A1045366-96E7-46BB-8C93-CFD28359DD9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f021f5fad625a2d1b7ae69973379640bb5c12aef","datavalue":{"value":{"entity-type":"item","numeric-id":5386139,"id":"Q5386139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$261E49C2-4CE9-42E4-ABF8-2E4E7D684900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666d1d256fe16d5067471fe53e33cc8fa9a85f26","datavalue":{"value":{"entity-type":"item","numeric-id":3663044,"id":"Q3663044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$E57DEA1B-4A99-419D-9790-EE22F77B578D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c56aaf8ccd46e3192e050c0368f83b3d69dc51b","datavalue":{"value":{"entity-type":"item","numeric-id":1277336,"id":"Q1277336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$4BF2F16D-34AA-4DD5-A520-247DE21B0339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa37c52f22d71444ff2effa0fe3ce6d3f742d7","datavalue":{"value":{"entity-type":"item","numeric-id":5905678,"id":"Q5905678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$CDC54FE9-D02D-4AB9-B807-385E6D23DE49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a118f4c4372e51856c754957bd9b998c241312b","datavalue":{"value":{"entity-type":"item","numeric-id":753819,"id":"Q753819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$92C08908-24A3-4FA9-A484-EBEF52251D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1093b3cebce1187f4c0ad54b1030a326683bc9b7","datavalue":{"value":{"entity-type":"item","numeric-id":5365071,"id":"Q5365071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$417725E3-B076-4196-82CE-8769E7120177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8494cb8104bcd64477a7b1c0a71c10275cef2968","datavalue":{"value":{"entity-type":"item","numeric-id":3440269,"id":"Q3440269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$CD4AC2DD-8176-4F33-80F8-906E0F172F57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aac3166833b1071eff04bf2728ae72a8cbc72a4","datavalue":{"value":{"entity-type":"item","numeric-id":557836,"id":"Q557836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$6C8EAE71-6958-467F-BC50-0F92D92858EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2e9b3d4894f3739abe95fe62d00a87db18c64ef","datavalue":{"value":{"entity-type":"item","numeric-id":1408380,"id":"Q1408380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$EF391E23-551A-4E14-8113-EC58AD9F33BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b5fa8fb11c78aae21b2eb5b72be3dfa58615b97","datavalue":{"value":{"entity-type":"item","numeric-id":4037693,"id":"Q4037693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$2356758B-4688-4285-A3F4-CB47CD014958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4afd6af18f6b3e851b76214fa76a694c5f4b58bc","datavalue":{"value":{"entity-type":"item","numeric-id":5172728,"id":"Q5172728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$980E0857-62B8-4966-B9E1-8A39B1B8074C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2e8b3043a749599c818e819583afcfaa93c3165","datavalue":{"value":{"entity-type":"item","numeric-id":1575269,"id":"Q1575269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$BBBB23EB-F24E-4CD6-BB94-87C13BC30D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5ea73ec7888502cdec2962bf0b4bfed2af0ad3d","datavalue":{"value":{"entity-type":"item","numeric-id":3113785,"id":"Q3113785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$B2905093-ABE7-496D-83F5-E52E2D182CD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"def643ba426dace1e4379bfd001d506cb1e71a1d","datavalue":{"value":{"entity-type":"item","numeric-id":1408387,"id":"Q1408387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$E33A2E84-4005-491E-80AE-77B2CE0281E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50041fd827b9a880db5475227f379529c471731","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377802$49481FBF-1A5B-4B8A-94BD-658752AFC505","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c4afb37f947bfb542555f3712d1b02abeb9140a6","datavalue":{"value":"10.1007/S00493-012-2679-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377802$93FC4B1B-7EB1-41F7-9833-88667B156818","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56922a4e9d51d5955bc9357b679e25f77a23d847","datavalue":{"value":{"entity-type":"item","numeric-id":3639289,"id":"Q3639289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"322ae449e9451d2892219c41bef5db5f96a9df57","datavalue":{"value":{"amount":"+0.8343420028686523","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":"Q377802$CB271A37-49B8-4DE6-B8FF-9EE28DDA9A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85ef8023e77e3b178af4c4e5f65f03e11bfe63e4","datavalue":{"value":{"entity-type":"item","numeric-id":3177819,"id":"Q3177819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36d3e892329f55220e8dfdb1d8997d5756943752","datavalue":{"value":{"amount":"+0.777893602848053","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":"Q377802$BBA52A7D-479C-4B37-ACBF-2A0EE9B3E978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ed2bb46d20de8e3a87b84b71be121989b490e13","datavalue":{"value":{"entity-type":"item","numeric-id":5365071,"id":"Q5365071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee211ffbabb39230c8b5de0c89c4e2f42b8e92b6","datavalue":{"value":{"amount":"+0.729485809803009","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":"Q377802$F6CDD098-C0F7-4256-AA89-C99CE62C900C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9b0c0142bcb4f97beb87cdc2e5741d284d0fa22","datavalue":{"value":{"entity-type":"item","numeric-id":1396655,"id":"Q1396655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35db6531d010b45ee4d448531e41de5c4b81e91d","datavalue":{"value":{"amount":"+0.6839305758476257","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":"Q377802$91D0D504-4344-4FF2-9273-468FEF4C4193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f485824cbb35d0d953e1429024addc0480075c12","datavalue":{"value":{"entity-type":"item","numeric-id":4952609,"id":"Q4952609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c523a7830a422ff8c4c6ac06a85da6ab09b996a","datavalue":{"value":{"amount":"+0.6839302778244019","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":"Q377802$0409E880-C1BF-4E3D-A4EA-EC73971C7549","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Disproof of the neighborhood conjecture with implications to SAT","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Disproof_of_the_neighborhood_conjecture_with_implications_to_SAT"}}}}}