全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Value Constraint and Monotone circuit

Full-Text   Cite this paper   Add to My Lib

Abstract:

This paper talks about that monotone circuit is P-Complete. Decision problem that include P-Complete is mapping that classify input with a similar property. Therefore equivalence relation of input value is important for computation. But monotone circuit cannot compute the equivalence relation of the value because monotone circuit can compute only monotone function. Therefore, I make the value constraint explicitly in the input and monotone circuit can compute equivalence relation. As a result, we can compute P-Complete problem with monotone circuit. We can reduce implicit value constraint to explicit with logarithm space. Therefore, monotone circuit is P-Complete.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133