(۲۴ تیر ۱۳۹۰ ۱۲:۰۷ ق.ظ)admin نوشته شده توسط: در نظریه محاسبه پذیری اگر A به B در زمان چند جملهای کاهش پذیر بوده و B تصمیم ناپذیر باشد آن گاه Aنیز تصمیم ناپذیر خواهد بود.
(۲۴ تیر ۱۳۹۰ ۰۴:۲۶ ب.ظ)parimehraban نوشته شده توسط: در نظریه محاسبه پذیری اگر A به B کاهش پذیر بوده و B تصمیم پذیر باشد آن گاه Aنیز تصمیم پذیر خواهد بود .همین طوراگر A تصمیم پذیر نبوده و به B کاهش یابد، آنگاه B نیز تصمیم پذیر نخواهد بود .
(۲۷ آذر ۱۳۹۰ ۱۱:۳۹ ب.ظ)psps1368 نوشته شده توسط: مثلا Halting Problem یک مسئله NP-Hard است، چرا که SAT به آن در زمان چند جمله ای کاهش پیدا می کند. واضح هست که Halting Problem، یک مسئله NP نیست.
با توجه به توضیحات بالا، یه سوال دارم.
اگر A در زمان چندجمله ای به B کاهش پیدا کنه، اگرA یه مساله NPC باشه می شه گفت که B یه مساله NPC هست یا اگر B یه مساله NPC می شه گفت که A هم NPC هست؟؟
در واقع سوالم اینه که اگر A و B هر دو تصمیم پذیر باشند یعنی جزو P باشند اونوقت اگر A جزو مسائل P باشه، B هم P می شه و اگر B تصمیم پذیر یا جزو NPC باشه اونوقت َA هم NPC می شه؟