Tautologies with a unique craig interpolant, uniform vs. nonuniform complexity
Tautologies with a unique craig interpolant, uniform vs. nonuniform complexity
复制标题
具有独特 craig 插值的同义反复、均匀复杂性与非均匀复杂性
DOI：
10.1016/0168-0072(84)90029-0
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
D. Mundici
中科院分区：
文献类型：
--
作者：
D. Mundici
⊆{0，1}；*AND‘={0，1}*\→都是在某个不确定的时间范围内被识别的，然后，在不多的时间内，人们可以写下具有唯一内插的∩A’n的重言式逻辑；因此，如果一个人能够快速地找到唯一的内插，那么对于某个固定的p\S和gt；0，可以在确定的时间内识别Sp。一般而言，对于句子逻辑中寻找唯一内插的问题，复杂性度量产生了电路深度与非确定性图灵时间以及证明长度与逻辑理论决策过程的复杂性之间的新关系。
IfS⊆{0,1};*andS′ = {0,1}*\sbSare both recognized within a certain nondeterministic time boundTthen, in not much more time, one can write down tautologiesAn→A′nwith unique interpolantsInthat defineS∩{0,1}n; hence, if one can rapidly find unique interpolants, then one can recognizeSwithin deterministic timeTpfor some fixedp\s>0. In general, complexity measures for the problem of finding unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories.