בעיית תת-קבוצות זרות

מתוך ויקיפדיה, האנציקלופדיה החופשית

בעיית תת-קבוצות זרות היא בעיה פתוחה במדעי המחשב, העוסקת בשאלה: בהינתן קבוצה של קבוצות, כמה מתוכן ניתן לקחת כך שהן יהיו קבוצות זרות בזוגות? שאלה זו היא NP-קשה. השאלה: האם יש k קבוצות כאלה? היא NP-שלמה.

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.