Hello, this is beta version of diophantus. If you want to report about a mistake, please, write to
hello@diophantus.org
pdf
Complexity Considerations, cSAT Lower Bound
Abstract. This article discusses completeness of Boolean Algebra as First Order Theory
in Goedel's meaning. If Theory is complete then any possible transformation is
equivalent to some transformation using axioms, predicates etc. defined for
this theory. If formula is to be proved (or disproved) then it has to be
reduced to axioms. If every transformation is deducible then also optimal
transformation is deducible. If every transformation is exponential then
optimal one is too, what allows to define lower bound for discussed problem to
be exponential (outside P). Then we show algorithm for NDTM solving the same
problem in O(n^c) (so problem is in NP), what proves that P \neq NP.
Article proves also that result of relativisation of P=NP question and oracle
shown by Baker-Gill-Solovay distinguish between deterministic and
non-deterministic calculation models. If there exists oracle A for which
P^A=NP^A then A consists of infinite number of algorithms, DTMs, axioms and
predicates, or like NDTM infinite number of simultaneous states.
Reviews
There are no reviews yet.
Comments
Log in to leave a comment.
Reviews
There are no reviews yet.
Log in to leave a review.
There are no comments yet.