مرزهای وزن و چگالی ترکیبی در نمایش تابع آستانه چند جمله ای توابع بولی

عنوان مرزهای وزن و چگالی ترکیبی در نمایش تابع آستانه چند جمله ای توابع بولی
نویسنده اوزتوپ، ارهان، اسدا، م.
تاریخ انتشار: 2022-08
محل انتشار - الزویر
موضوع تابع خم، تابع بولی، نمایش علامت چند جمله ای، تابع آستانه چند جمله ای، تابع پراکنده
نوع دوره ای
زبان انگلیسی
دیجیتال بله
نسخه خطی خیر
کتابخانه: دانشگاه اوزیغین
شناسه دارایی کتابخانه 0012-365X
شماره ثبت 5d156e90-f981-41b0-98be-1d2071eab8c7
محل کتابخانه علوم کامپیوتر
تاریخ 2022-08
یادداشت‌ها دانشگاه اوزاکا
متن نمونه در گزارش قبلی نشان داده شد که یک تابع بولی n-متغیر دلخواه f را می توان به عنوان یک تابع آستانه چند جمله ای (PTF) با تعداد 0.75×2n یا کمتر از تک جمله ها نشان داد. در این گزارش، یک کران بالایی بر روی قدر مطلق وزن‌های (عدد صحیح) یک PTF استخراج می‌کنیم که نشان‌دهنده f است و همچنان از کران چگالی فوق‌الذکر تبعیت می‌کند. طبق دانش ما، این بهترین کران ترکیبی را بر روی چگالی PTF (تعداد تک‌جملات) و وزن PTF (مجموع بزرگی‌های ضریب) توابع بولی عمومی ارائه می‌کند. برای مورد خاص توابع خمیده، مشخص شد که هر تابع خمش متغیر n را می توان با ضرایب صحیح کمتر یا مساوی 2n با چگالی بیش از 0.75×2n نشان داد، و برای مورد توابع بولی m-sparse که تقریباً ثابت هستند به جز برای کوچک (m≪2n)، تعداد متغیرهای کوچک (m≪2n) را می توان با تعداد PT نشان داد که با انتساب کوچک می توان آنها را نشان داد. چگالی حداکثر m+2n-1. علاوه بر این، محدودیت‌های وزنی محکم PTF با انطباق با مرز چگالی 0.75×2n به صورت عددی برای توابع بولی عمومی تا 6 متغیر به‌دست می‌آیند.
DOI 10.1016/j.disc.2022.112912
Cilt 345
مشاهده در منبع دانشگاه اوزیغین دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات
دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات دانشگاه اوزیغین

مرزهای وزن و چگالی ترکیبی در نمایش تابع آستانه چند جمله ای توابع بولی

نویسنده اوزتوپ، ارهان، اسدا، م.
تاریخ انتشار 2022-08
محل انتشار - الزویر
موضوع تابع خم، تابع بولی، نمایش علامت چند جمله ای، تابع آستانه چند جمله ای، تابع پراکنده
نوع دوره ای
زبان انگلیسی
دیجیتال بله
نسخه خطی خیر
کتابخانه دانشگاه اوزیغین
شناسه دارایی کتابخانه 0012-365X
شماره ثبت 5d156e90-f981-41b0-98be-1d2071eab8c7
محل کتابخانه علوم کامپیوتر
تاریخ 2022-08
یادداشت‌ها دانشگاه اوزاکا
متن نمونه در گزارش قبلی نشان داده شد که یک تابع بولی n-متغیر دلخواه f را می توان به عنوان یک تابع آستانه چند جمله ای (PTF) با تعداد 0.75×2n یا کمتر از تک جمله ها نشان داد. در این گزارش، یک کران بالایی بر روی قدر مطلق وزن‌های (عدد صحیح) یک PTF استخراج می‌کنیم که نشان‌دهنده f است و همچنان از کران چگالی فوق‌الذکر تبعیت می‌کند. طبق دانش ما، این بهترین کران ترکیبی را بر روی چگالی PTF (تعداد تک‌جملات) و وزن PTF (مجموع بزرگی‌های ضریب) توابع بولی عمومی ارائه می‌کند. برای مورد خاص توابع خمیده، مشخص شد که هر تابع خمش متغیر n را می توان با ضرایب صحیح کمتر یا مساوی 2n با چگالی بیش از 0.75×2n نشان داد، و برای مورد توابع بولی m-sparse که تقریباً ثابت هستند به جز برای کوچک (m≪2n)، تعداد متغیرهای کوچک (m≪2n) را می توان با تعداد PT نشان داد که با انتساب کوچک می توان آنها را نشان داد. چگالی حداکثر m+2n-1. علاوه بر این، محدودیت‌های وزنی محکم PTF با انطباق با مرز چگالی 0.75×2n به صورت عددی برای توابع بولی عمومی تا 6 متغیر به‌دست می‌آیند.
DOI 10.1016/j.disc.2022.112912
Cilt 345
دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات
دانشگاه اوزیغین شما در حال هدایت مجدد هستید...

لطفاً صبر کنید