General Mathematics

   

Input Relation and Computational Complexity

Authors: Koji KOBAYASHI

This paper describes about complexity of PH problems by using "Almost all monotone circuit family" and "Accept input pair that sandwich reject inputs". 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)). Therefore, we can find out DTM limitation by using this "NNF Circuit family". To clarify NNF circuit family limitation, we pay attention to AND-gate and OR-gate relation. If two accept "Neighbor input" pair that sandwich reject "Boundary input" in Hamming distance, NNF circuit have to meet these different variables of neighbor inputs in AND-gate to differentiate boundary inputs. NNF circuit have to use unique AND-gate to identify such neighbor input. The other hand, we can make neighbor input problem "Neighbor Tautology DNF problem (NTD)" in PH. NTD is subset of tautology DNF that do not become tautology if proper subset of one variable permutate positive / negative. NTD include many different variables which number is over polynomial size of input length. Therefore NNF circuit family that compute NTD are over polynomial size of length, and NTD that include PH is not in P.

Comments: 18 Pages.

Download: PDF

Submission history

[v1] 2018-03-06 10:43:29
[v2] 2018-03-09 23:22:52
[v3] 2018-03-13 11:14:01
[v4] 2018-03-17 11:32:08
[v5] 2018-03-24 00:38:31
[v6] 2018-03-27 08:31:42

Unique-IP document downloads: 635 times

Vixra.org 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. Vixra.org 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