首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 AnA′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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号