已知L1是NP完全问题,L1可以规约为L2,L2不属于NP,则L2是NP完全问题吗
时间: 2024-05-18 09:14:30 浏览: 65
如果L1可以多项式时间规约为L2,且L2不属于NP,那么L2不一定是NP完全问题。
根据定义,如果L2是NP完全问题,那么L2必须属于NP,并且所有NP问题都可以多项式时间规约为L2。
但是,由于L2不属于NP,它不能包含所有NP问题的解,因此L2不可能是NP完全问题。
因此,L1可以规约为L2,L2不属于NP时,我们只能得出L2不是NP问题,而不能得出L2是NP完全问题的结论。
阅读全文