عباس چراغی،
دوره 14، شماره 2 - ( 5-1393 )
چکیده
در یک طرح تقسیم راز دوبخشی، مجموعه سهام¬داران را به دو قسمت چنان تقسیم می¬کنند که همه سهام¬داران درون یک بخش، نقش یکسانی را بازی کنند. پادرو و سائز ساختارهای دسترسی ایده¬آل دو بخشی را به طور کامل دسته بندی کرده¬اند اما اینکه کدام ساختارهای دسترسی غیرایده¬آل پیچیدگی بهینه دارند همچنان نامعلوم است. از طرفی مشخص کردن پیچیدگی ساختارهای دسترسی در حالت کلی، یکی از بزرگترین مسائل حل نشده در بحث تقسیم راز است. به این منظور و در راستای بررسی پیچیدگی، ما خودمان را به ساختارهای دسترسی دو بخشی محدود می¬کنیم تا روش جدیدی برای محاسبه کران¬هایی روی پیچیدگی بهینه این گونه ساختارها بدست آوریم. در این مقاله با استفاده از ارتباط طرح¬های تقسیم راز و پلی¬ماتریدها، برای پیچیدگی هر ساختار دسترسی دوبخشی، از یک مساله برنامه¬ریزی خطی استفاده می¬کنیم تا یک کران پایین روی پیچیدگی هر ساختار دسترسی ارائه دهیم. ساختارهای دسترسی که ما در این مقاله بررسی کرده¬ایم محدودیتی در تعداد سهام¬داران شرکت کننده در طرح ندارند. به علاوه در این مقاله نشان خواهیم داد که برخی از کران¬های پایین ارائه شده بر روی پیچیدگی این ساختارهای دسترسی دقیق هستند. در آخر طرح¬های بهینه جدیدی را بر روی ساختارهای دسترسی دوبخشی خاص ارائه خواهیم داد.
