p≠np假设下np-npc-p中自然问题的一个候选者

1975年,lander证明在p≠np假设下存在一个语言属于np-npc-p(npi).但lander给出语言并不是一个自然的语言因在该语言的构造中需运行所有多项式时间的图灵机.迄今为止,还没有自然的语言被证明在p≠np假设下属于npi,并且在p≠np假设下寻找一个属于npi的自然语言是一个重要的未解决问题.作者部分解决了此长期未解决的问题.定义了2+f(m)-hast模型.基于该模型，给出了在p≠np假设下np-npc-p中自然问题的一个候选者.已证明在p≠np假设下它不属于npc并且在更强但合理的假设下它的确属于npi.