计算模整数NP解的时空权衡及其局限性验证

计数模整数NP解的时空权衡卡内基梅隆大学0-0介绍1空间有界条件下介绍1-a空间有界条件下• SAT和QUANTIFIED BOOLEAN FORMULAS的时空权衡[ Santhanam介绍1-B空间有界条件下• SAT和QUANTIFIED BOOLEAN FORMULAS的时空权衡[ Santhanam• S AT需要<$（n2cos（π/7））<$n1。使用no（1）空间的RAM上的801时间也适用于VERTEXCOVER、HAMILTONIANPATH、MAXCUT等。介绍1-C空间有界条件下• SAT和QUANTIFIED BOOLEAN FORMULAS的时空权衡[ Santhanam• S AT需要<$（n2cos（π/7））<$n1。使用no（1）空间的RAM上的801时间也适用于VERTEXCOVER、HAMILTONIANPATH、MAXCUT等。类似的局限性能否在其他问题上得到证明？介绍1-D空间有界条件下• SAT和QUANTIFIED BOOLEAN FORMULAS的时空权衡[ Santhanam• S AT需要<$（n2cos（π/7））<$n1。使用no（1）空间的RAM上的801时间也适用于VERTEXCOVER、HAMILTONIANPATH、MAXCUT等。类似的局限性能否在其他问题上得到证明？[Diehl-Van Melkebeek]，[Viola]使用随机算法介绍2介绍2-a设m是一个固定的整数，m是一个组合问题.一个给定例子的解的个数能被m整除吗？介绍2-B设m是一个固定的整数，m是一个组合问题.一个给定例子的解的个数能被m整除吗？MODmSAT：对于公式F，解的个数是否能被m整除？[Cai-Hemachandra'92]定义MODmP，其中MODmSAT是一个完整的问题。介绍2-C设m是一个固定的整数，m是一个组合问题.一个给定例子的解的个数能被m整除吗？MODmSAT：对于公式F，解的个数是否能被m整除？[Cai-Hemachandra'92]定义MODmP，其中MODmSAT是一个完整的问题。最近的关注：由Valiant的偶然算法推动-对于某些P -完全问题，• 可以确定P中的解的个数是否• 但是MOD2P -很难确定解的个数是否能被2整除MODmP的复杂性3MODmP的复杂性一般来说，MODMSAT有多难（它和S一样难吗？）是不是很难？）3-aMODmP的复杂性一般来说，MODMSAT有多难（它和S一样难吗？）是不是很难？）3-B• （Valiant-Vazirani）RP-从SAT减少到MODmSAT• （Naik-Regan-Sivakumar）从SAT到MOD2SAT的O（n·poly（logn）• （户田荻原、古普塔）从随机SAT到MOD2SAT的时间复杂度为O（nk+1）-随机2边DMODmP的复杂性一般来说，MODMSAT有多难（它和S一样难吗？）是不是很难？）3-C• （Valiant-Vazirani）RP-从SAT减少到MODmSAT• （Naik-Regan-Sivakumar）从SAT到MOD2SAT的O（n·poly（logn）• （户田荻原、古普塔）从随机SAT到MOD2SAT的时间复杂度为O（nk+1）-随机2边D对于MODmS在下限的朴素想法：通过应用上述约简并诉诸已知的S AT下界来证明MOD m S AT的下界。主要障碍：随机性4主要障碍：随机性4-a• Can’t use Valiant-Vazirani reduction or its因为它们主要障碍：随机性4-B• Can’t use Valiant-Vazirani reduction or its因为它们• 即使我们能使它们节省空间，我们也只能说：MODMS AT有一个快速的检测器。alg. S AT的速度很快。alg.但是我们主要障碍：随机性4-C• Can’t use Valiant-Vazirani reduction or its因为它们• 即使我们能使它们节省空间，我们也只能说：MODMS AT有一个快速的检测器。alg. S AT的速度很快。alg.但是我们• 我们能摆脱随机性吗？主要障碍：随机性4-D• Can’t use Valiant-Vazirani reduction or its因为它们• 即使我们能使它们节省空间，我们也只能说：MODMS AT有一个快速的检测器。alg. S AT的速度很快。alg.但是我们• 我们能摆脱随机性吗？• 去随机化？ 我们(But我们有充分的理由相信它们的存在[Klivans-Van Melkebeek]）5主要结果