مسئله تناظر پست

یک نمونه از مسئلهٔ تناظر پست را این‌گونه تعریف می‌کنیم:

هر نمونه از این مسئله شامل دو لیست از رشته‌هایی است که بر روی الفبای ${\displaystyle \mathrm{\Sigma }}$

${\displaystyle A=x_1,x_2,...,x_k}$

${\displaystyle B=y_1,y_2,...,y_k}$

برای هر ${\displaystyle i}$

جواب مسئلهٔ تناظر پست را نیز این‌گونه تعریف می‌کنیم:

برای یک نمونه از مسئله جواب وجود دارد اگر دنباله‌ای از اعداد صحیح مانند ${\displaystyle i_1}$

${\displaystyle x_{i_1}{x}_{i_2}..x_{i_n}=y_{i_1}{y}_{i_2}..y_{i_n}}$

پس به‌طور کلی مسئلهٔ تناظر پست این‌گونه تعریف می‌شود:

«آیا برای یک نمونه از مسئلهٔ تناظر پست جوابی وجود دارد یا خیر؟»

فرض کنید ${\displaystyle \mathrm{\Sigma }=\{a,b\}}$