{"entities":{"Q1084375":{"pageid":1095127,"ns":120,"title":"Item:Q1084375","lastrevid":66104766,"modified":"2026-04-12T07:35:07Z","type":"item","id":"Q1084375","labels":{"en":{"language":"en","value":"The complexity of central slice functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3978980"}},"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":"Q1084375$33D652FA-B566-4902-AB5B-726A4CD74FE4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f3b684fcabe0277d3b45ddcce18e1705ee80c599","datavalue":{"value":{"text":"The complexity of central slice functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084375$2211409F-CA05-41C4-B36C-DC3A5BB97C85","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9d7023c44e9748ef2a95d2038adb0948753f8f3b","datavalue":{"value":"0605.94010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084375$75992F98-32C3-4827-960B-9A4DA1E33EC4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec92bbd7f2054acba6d4fa736cb8a9ac2484a860","datavalue":{"value":"10.1016/0304-3975(86)90122-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084375$151BD6ED-EAD9-4A0D-8A66-55A8737DF52B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a266e429b8e23469baa7cd769b303cf70be10d1c","datavalue":{"value":{"entity-type":"item","numeric-id":324698,"id":"Q324698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$F0A25429-549E-461C-8F85-03B4FB27768F","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":"Q1084375$9D6E80C3-AD42-43AF-AEB7-97360DF70BB6","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":"Q1084375$7FDC5835-918F-4DFD-A7A6-AABE400D0A64","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4b099f855fb2f36446512a0c729364bcc2f578d9","datavalue":{"value":"The k-slice of a Boolean function \\(f(x_ 1,...,x_ n)\\) is the function \\(f_ k=(f\\wedge T^ n_ k)\\vee T^ n_{k+1}\\), where \\(T^ n_ k\\) is the k-th threshold function. Berkowitz has shown that the nonmonotone combinational and monotone circuit complexities of any k-slice function differ by at most an additive term of O(n log\\({}^ 2 n)\\). In addition, the fact that \\(f=\\bigvee^{n}_{k=1}(E^ n_ k\\wedge f_ k)\\), where \\(E^ n_ k=\\neg T^ n_{k+1}\\wedge T^ n_ k\\), implies that if f is ''hard'' then some slice of f must have large monotone complexity. However, this latter result does not specify any particular slice and it is known that some (nontrivial) slices of NP-complete Boolean functions have linear complexity. In this paper three basic NP-complete monotone Boolean functions are examined: n/2-cliques, Hamiltonian circuits, and satisfiability. It is proved that the N/2-slice (called central slice) is NP-complete for each of these functions, where N is the total number of variables \\((N=n(n-1)/2\\) for the first two functions).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084375$B50D2B66-C3B3-4DEA-95B1-B3ACE038B503","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084375$2B1A430C-ED45-4BAE-8882-4BCC37C3C3F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084375$BD0C3C90-EFFF-45EC-AA21-1608D96E17DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084375$B8687CCA-F33A-4314-8750-29DAED966EBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084375$26260233-7555-4F2D-B712-486C79260B0B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"596c11b1608fbf0cf5a7d10b1b7bd35c8168e034","datavalue":{"value":"3978980","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084375$BF1F86B8-EDD7-4043-B289-4C98A9C0A48B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f25e35fc42cf13b8289b2fa1c7d8b546d4d2ade8","datavalue":{"value":"combinational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084375$7602A50B-44D2-4D54-86A7-A30256F209AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c601bd810a5a1256b1b65c8bd40ab071ba901b55","datavalue":{"value":"monotone circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084375$31379A02-6FC3-4AEA-A1DB-94237734472F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084375$BE0E0903-7147-40FE-A86A-296C5EBC7C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50401a89f383857ee6fcf2adcb0261f2bd97bb00","datavalue":{"value":"k-slice of a Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084375$F7FE9EAE-7098-4008-826E-D2C6BF2C0A13","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1833d190eb6492ca84e0c93a6ff12de5694705d3","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$18985BF0-8505-44A3-8123-BAD6890A07E8","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":"Q1084375$C731BF1F-66AA-408C-8EA5-D15ED02990D9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9108abe6915cd0cc277ec91c9276c91892807bb3","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90122-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1084375$DA2C49F2-27B1-4F06-A79D-03ADB1AE87ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e4f8429502e1e86301ae1cde76afa1fd9880161a","datavalue":{"value":"W2051306408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084375$930AA37D-D876-4FB7-A791-4178C8D39C69","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$5A07F8D0-FF49-4FBA-A37C-17545AD5D574","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58af9a438ca79f17e01d4568050919b82873e432","datavalue":{"value":{"entity-type":"item","numeric-id":794625,"id":"Q794625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$727F2B9D-70EC-475B-A768-FA7F20B4BAD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"033caf9d16e4e97485da89b82da6f481f16730c9","datavalue":{"value":{"entity-type":"item","numeric-id":1121853,"id":"Q1121853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$B4BED4EA-EEF8-4E56-A0B0-797EF26178CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0942c3ffeac8339c20eccc6667aba9b8af08cc5f","datavalue":{"value":{"entity-type":"item","numeric-id":3758729,"id":"Q3758729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$0A912301-061A-42C4-8A31-5ACDD28814BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e822d0f6871d5df9de9fd97a15be05d850e629","datavalue":{"value":{"entity-type":"item","numeric-id":1071001,"id":"Q1071001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$6BC21D83-2232-473B-89C9-FA3B39DE0AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51e06cd08b21ba41692bb65b88d6aafecf32e6a8","datavalue":{"value":{"entity-type":"item","numeric-id":4726175,"id":"Q4726175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$DFD83684-00A5-422B-97D3-DE42F79F04CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f570b901946254e7e256906c632b0bf64e27f322","datavalue":{"value":{"entity-type":"item","numeric-id":1166489,"id":"Q1166489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$FB499D94-1A22-4ABE-B9E2-E713F6710B8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6daeb38a6c68932fc6cb9ea616cde11191fce94d","datavalue":{"value":{"entity-type":"item","numeric-id":1066866,"id":"Q1066866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$BB141AB4-8C1A-4944-861C-B1C79C52E5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00202a51d2d07ca7e1551385926163c5413f0c30","datavalue":{"value":{"entity-type":"item","numeric-id":1079365,"id":"Q1079365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084375$BB0D0818-0EAD-43CA-AE9B-E36722631105","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49f389d6009550bbc5f2de2c54600e6d8cda5155","datavalue":{"value":{"entity-type":"item","numeric-id":1079365,"id":"Q1079365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"989702d41afb8a6ceeee86edae38c3cdd343ddac","datavalue":{"value":{"amount":"+0.8668792247772217","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":"Q1084375$CB012658-E34B-47CF-B995-48F8605C350D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17980287b4aff10463631316346dae81267a0f62","datavalue":{"value":{"entity-type":"item","numeric-id":3221885,"id":"Q3221885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d8d239ab084824a506b2e1ff3d56af0c21f3113","datavalue":{"value":{"amount":"+0.853912889957428","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":"Q1084375$EA94E5AD-43F6-4DED-9623-C4FD36417EF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38d6d711695922bc175ba3dfeb5ef493de043b60","datavalue":{"value":{"entity-type":"item","numeric-id":4726175,"id":"Q4726175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ecdefeb1891cc0014ce109dc49120c0eb528eac","datavalue":{"value":{"amount":"+0.8449192047119141","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":"Q1084375$ED7AD614-6C24-4874-B506-CAE00627B378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fb0b9b4016c72e33d1ce660b4141a3a117dde3a","datavalue":{"value":{"entity-type":"item","numeric-id":1066866,"id":"Q1066866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd364cca7a15820e3ebaa7c8571e71c708c9ec83","datavalue":{"value":{"amount":"+0.8321109414100647","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":"Q1084375$F548704D-1FAB-44CD-B4F2-908E8B985639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da871f72715a06bf28eead957668a72b79f41eee","datavalue":{"value":{"entity-type":"item","numeric-id":1121853,"id":"Q1121853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11297edd6098b40d8c409e3ab48a69bde9b5234a","datavalue":{"value":{"amount":"+0.829296886920929","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":"Q1084375$209EAE30-DEE0-417A-852E-F9A3D4E93B84","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of central slice functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_central_slice_functions"}}}}}