General Mathematics


Almost All Monotone Circuit Family

Authors: Koji KOBAYASHI

This paper describes about "Almost all monotone circuit family" and introduce its interesting advantages to measuring problem complexity. Explained in Michael Sipser "Introduction to the Theory of COMPUTATION", circuit family that emulate Deterministic Turing machine (DTM) are almost all monotone circuit family except some NOT-gate that connect input variables (like negation normal form (NNF)). This "NNF Circuit family" have good characteristic which present each accept input exclusivity and symmetry. Each input make some INPUT-gate and NOT-gate output 1 which set is different from another input, and meet these output in OR-gate and finally connect (specified) OUTPUT-gate. That is, NNF circuit start accept input that exclusive each other, and meet each input as symmetry input step by step and finally goal same output. Especially, some different variables which sandwich reject inputs correspond to unique AND-gate. That is, we can measure problem complexity by using different variables of accept inputs. For examples, such number of different variables type of negation HornSAT is at most polynomial size. This is one of reason that we can compute P problem easily.

Comments: 12 Pages.

Download: PDF

Submission history

[v1] 2018-03-24 00:41:03
[v2] 2018-03-25 05:56:51
[v3] 2018-03-26 06:48:03

Unique-IP document downloads: 41 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus