Tautologies with a unique craig interpolant,uniform vs. nonuniform complexity |
| |
Authors: | Daniele Mundici |
| |
Institution: | National Research Council, and Mathematical Institute of the University of Florence, Loc. Romola N.76, 50060 Donnini, Florence, Italy |
| |
Abstract: | If S?{0,1};* and S′ = {0,1}*\sbS are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies An→A′n with unique interpolants In that define S∩{0,1}n; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time Tp for some fixed p\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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|