本页使用了标题或全文手工转换

多项式时间归约

维基百科,自由的百科全书
跳到导航 跳到搜索

计算复杂性理论中,多项式时间归约是指假设已有解决一个问题的子程序,利用它在多项式时间内(不考虑子程序运行所用时间)解决另一个问题的归约方法。多项式时间归约有几种不同类型,取决于具体如何使用子程序。