مسئله تطابق سه‌بعدی
تطابق سه‌بعدی در نظریه گراف تعمیم تطابق دوبخشی (تطابق دوبعدی) به ۳ ابرگراف یک‌شکل است. پیدا کردن بزرگ‌ترین تطابق سه‌بعدی یک مسئلۀ ان‌پی-سخت مشهور در نظریه پیچیدگی محاسباتی است.
فرض کنید formula_1، formula_2 و formula_3 مجموعه‌های متناهی مجزا باشند و formula_4 یک زیرمجموعه از formula_3 × formula_2 × formula_1 باشد. یعنی formula_4 شامل ۳ تایی‌های formula_9 است به طوری که formula_1 ∋ formula_11، formula_2 ∋ formula_13 و formula_3 ∋ formula_15.formula_4 ⊇ formula_17 یک تطابق سه‌بعدی است در صورتی که به ازای هر دو سه‌تایی مجزا formula_17 ∋ (formula_19) و formula_17 ∋ (formula_21) داشته باشیم: formula_22≠formula_23 formula_24≠formula_25 و formula_26≠formula_27
شکل سمت چپ صفحه تطابق‌های سه‌بعدی را نشان می‌دهد. formula_1 با نقاط قرمز، formula_2 با نقاط آبی و formula_3 با نقاط سبز نشان داده شده‌است. شکل الف مجموعۀ formula_4 (نواحی خاکستری) را نشان می‌دهد. شکل ب یک تطابق سه‌بعدی formula_17 با ۲ = |formula_17| را نشان می‌دهد و شکل پ یک تطابق سه‌بعدی formula_17 با ۳ = |formula_17| را نشان می‌دهد.
تطابق formula_17 که در شکل پ نشان داده‌شده‌است یک تطابق سه‌بعدی بیشینه است، یعنی |formula_17| را بیشینه می‌کند. تطابق‌های نشان داده‌شده در شکل‌های ب و پ تطابق‌های سه‌بعدی ماکسیمال هستند، یعنی نمی‌توان با افزودن عضوهای بیش‌تری از formula_4 آن‌ها را گسترش داد.
یک تطابق دوبعدی را می‌توان به‌طور کاملاً مشابه تعریف کرد. فرض کنید formula_1 و formula_2 مجموعه‌های متناهی مجزا باشند و formula_4 یک زیرمجموعه از formula_1 × formula_2 باشد. formula_4 ⊇ formula_17 یک تطابق دوبعدی است در صورتی که برای هر دو زوج مجزای formula_17 ∋ (formula_47) و formula_17 ∋ (formula_49) داشته باشیم: formula_22 ≠ formula_23 و formula_24 ≠ formula_25.
در تطابق دوبعدی، مجموعۀ formula_4 را می‌توان به صورت مجموعۀ یال‌ها در یک گراف دوبخشی (formula_55) = formula_56 تعبیر کرد؛ هر یال formula_4 یک رأس از formula_1 را به یک رأس از formula_2 متصل می‌کند و یک تطابق دوبعدی یک تطابق در گراف formula_56 است، یعنی مجموعه‌ای از یال‌های دوبه‌دو غیرمجاور.
از این رو تطابق‌های سه‌بعدی را می‌توان به صورت تعمیم تطابق به ابرگراف‌ها تعبیر کرد: مجموعه‌های formula_1، formula_2 و formula_3 شامل یال‌ها هستند، هر عضو formula_4 یک ابرگراف است و مجموعۀ formula_17 شامل یال‌های دوبه‌دو غیرمجاور است (یال‌هایی که رأس مشترک ندارند).
یک تطابق سه‌بعدی حالت خاصی از یک بسته بندی مجموعه است: می‌توانیم هر عضو (formula_66) از formula_4 را به عنوان یک زیرمجموعۀ {formula_66} از formula_3 ∪ formula_2 ∪ formula_1 تعبیر کنیم؛ پس یک تطابق سه‌بعدی formula_17 شامل زیرمجموعه‌های دوبه‌دو مجزا است.
در نظریه پیچیدگی محاسباتی، تطابق سه‌بعدی هم‌چنین نام مسئله تصمیم زیر است:
با داشتن مجموعۀ formula_4 و عدد صحیح formula_74، آیا یک تطابق formula_4 ⊇ formula_17 با formula_74 ≤ |formula_17| وجود دارد؟ این مسئلۀ تصمیم ان‌پی-کامل است؛ یکی از ۲۱ مسئله ان‌پی-کامل کارپ است.
این مسئله حتی در حالت خاص |formula_3| = |formula_2| = |formula_1| = formula_74 هم ان‌پی-کامل است. در این حالت یک تطابق سه‌بعدی نه تنها یک مسئله بسته‌بندی مجموعه است بلکه یک مسئله پوشش دقیق نیز هست: مجموعۀ formula_17 هر عضو formula_1، formula_2 و formula_3 را دقیقاً یک بار پوشش می‌دهد.
یک تطابق سه‌بعدی بیشینه یک بزرگترین تطابق سه‌بعدی است. در نظریه پیچیدگی محاسباتی، تطابق سه‌بعدی هم‌چنین نام مسئله بهینه‌سازی زیر است:
با داشتن مجموعۀ formula_4، یک تطابق سه‌بعدی formula_4 ⊇ formula_17 که |formula_17| را بیشینه می‌کند پیدا کنید.
از آنجا که مسئلۀ تصمیمی که در بالا آورده‌شد ان‌پی-سخت است، این مسئلۀ بهینه‌سازی ان‌پی-کامل می‌باشد و به نظر می‌آید که الگوریتمی چندجمله‌ای برای پیدا کردن یک تطابق سه‌بعدی بیشینه وجود ندارد. به هر حال، الگوریتم‌های چندجمله‌ای بهینه‌ای برای پیداکردن یک تطابق دوبخشی بیشینه (تطابق دوبعدی بیشینه) وجود دارند، برای مثال، الگوریتم هاپکرافت-کارپ.
این مسئله APX-کامل است، یعنی به سختی می‌توان آن را در حدود یک عدد ثابت تقریب زد. برای هر عدد مثبت ثابت ε>0، یک الگوریتم چندجمله‌ای (ε + ۳/۲)-تقریب برای تطابق سه‌بعدی وجود دارد.
یک الگوریتم خیلی سادۀ چندجمله‌ای ۳-تقریب برای تطابق سه‌بعدی وجود دارد: یک تطابق سه‌بعدی ماکسیمال بیابید. همان‌گونه که یک تطابق ماکسیمال در حدود عامل ۲ یک تطابق بیشینه است، یک تطابق سه‌بعدی ماکسیمال نیز در حدود عامل ۳ یک تطابق سه‌بعدی بیشینه است.