Classical Proof
- From: Martin Musatov <marty.musatov@xxxxxxxxx>
- Date: Wed, 13 May 2009 15:41:46 -0700 (PDT)
1
..
MARTIN M. MUSATOV
An open address to Mr. Stephen A. Cook
1. STATEMENT OF THE SOLUTION
This solution to P
PPPP versus N
NNNNP
PPPP explains how every language accepted by some
non deterministic algorithm in polynomial time can
be accepted by some (deterministic) algorithm in
polynomial time.To define the solution it is
formally it is necessary to observe the model of a
computer, or Turingmachine and process information
in real-time as it is received as a computable
function or linear stream.
Formally, the class P contains the in decision
problems
...P = <...@ NA...BP..
Let us continue the expansion:
D = EFG
(H + J)K = L MKN
OHNJKP.
(1+H)K =1+ KS +K(KPT)SV+.
YEH YEH
W(H)=JR+LXJKcos Z +[Ksin Z \
JG+[G = ^G
H = -[± a[G-4J^ 2J
dS=1+ H+HG+He+., -8<H<8
1!2! 3!
You may contact me at m.mm@xxxxxxxxxxxxxxxxxx to
arrange a computational demonstration of this proof
and polynomial time achievement.
Best regards,
Martin M. Musatov,
Los Angeles, CA, tel: 818.430.4586
This document contains mathematical formulations
and abstractions as they relate to functional
computing. It was completed on January 13,
2009 to be submitted to the arXiv.org Archive at
http://www.arxiv.org. It was completed with the
intent, since P=NP was solved by the author,
that the solver, Martin M. Musatov, has pursued the
conditions necessary, and met the conditions
required to be awarded and claim the Clay
Mathematics Institute Millennium prize. This paper
is submitted with the intent to be published across
other mediums. See the author for
more details.MMM.
....or...
BinaryChaosTheory.jpg
i
....... .. ............ .... ................
MARTIN M. MUSATOV
An Open Address to Mr. Stephen A. Cook
(r=0)
1. STATEMENT OF THE SOLUTION
T
his solution to P versus NP explains how every language accepted by
some non deterministic algorithm in polynomial
time can be accepted by some (deterministic) algorithm in polynomial
time. The central point in polar
coordinates, or the point with all zero coordinates (0, ..., 0) in
Cartesian coordinates is the binary point of origin [1]: .
In three dimensions, the x-axis, y-axis, and z-axis meet at the
origin.
The matrix form for these coordinates may be expressed: (#*)
The derivatives of the unit vectors are then: (#*)
To formally define the solution it is indeed necessary to observe the
model of a computer, or Turing machine and process
information in “real-time” as it is received as a computable function
or linear stream.
By this declaration, formally, the class P contains the indecision
problems
P = (#*)
.. (#*)
.... (#*)
.. (#*)
N
.. (#*)
.... (#*)
.. (#*)
P
From this point, we can continue the expansion:The area of a circle [2]: . ..=....2
The binomial theorem [3]: ..+.. ..= .. (#*)
... (#*)
.........-.. (#*)
... (#*)
...=0
Expansion of a sum (Taylor Series) [4];.
1+.. ..=1+
..... (#*)
1!
+
... ..-1 ..22!
+.
Followed by the Fourier Series [5]:.
... .. =..0+ ....cos
....... (#*)
... (#*)
+....sin
....... (#*)
... (#*)
8
...=1
The Pythagorean Formula [6]:. ..2+..2=..2
1 Arfken, G. "Special Coordinate Systems--Rectangular Cartesian
Coordinates." §2.3 in Mathematical Methods for Physicists, 3rd ed.
Orlando, FL: Academic
Press, pp. 94-95, 1985.
2 Richmond, Bettina (1999-01-12). "Area of a Circle". Western Kentucky
University. Retrieved on 2007-11-04.
3Amulya Kumar Bag. Binomial Theorem in Ancient India. Indian J.History
Sci.,1:68-74,1966.
4 "Neither Newton nor Leibniz - The Pre-History of Calculus and
Celestial Mechanics in Medieval Kerala". MAT 314. Canisius College.
Retrieved on
2006-07-09.
5William E. Boyce and Richard C. DiPrima, Elementary Differential
Equations and Boundary Value Problems, Eighth edition. John Wiley &
Sons,
Inc., New Jersey, 2005. ISBN 0-471-43338-1
6Bell, John L., The Art of the Intelligible: An Elementary Survey of
Mathematics in its Conceptual Development, Kluwer, 1999. ISBN
0-7923-5972-
0.
7Heaton, H. (1896) A Method of Solving Quadratic Equations, American
Mathematical Monthly 3(10), 236–237.
Through the Quadratic Equation [7]:.
...= (#*)
-..± ..2-4.... (#*)
2.. (#*)
To be succeed by a modified Taylor Series Expansion [8];.
.....=1+
... (#*)
1!
+
...22!
+
...33!
+.,-8<..<8
Martin M. Musatov, Los Angeles, CA, m.mm@xxxxxxxxxxxxxxxxxx tel:
818.430.4586
Feel free to contact me for a complete computational demonstration of
polynomial time achievement.
8Whittaker, E. T. and Watson, G. N. "Forms of the Remainder in
Taylor's Series." §5.41 in A Course in Modern Analysis, 4th ed.
Cambridge,
England: Cambridge University Press, pp. 95-96, 1990.
Stephen A. Cook
Distinguished University Professor
Department of Computer Science
University of Toronto
Toronto, Canada M5S 3G4
Tel: (416) 978-5183
sacook [at] cs [dot] toronto [dot] edu
I am a member of the Theory Group in the Computer Science Department.
....or...
Nondeterministic Polynomial-Time
Proof: published from:
http://qwiki.stanford.edu/wiki/Complexity_Zoo:N#np
02.24.2009, M.M.M.
If it is known that if any NP-complete language is sparse (contains no
more than a polynomial number of strings of length n), then P = NP.
[BH08] improved this result, showing that if any language in NP has an
NP-hard set of subexponential density, then coNP is contained in NP/
poly and thus, by [Yap82], PH collapses to the third level.
Conceptually, a decision problem is a problem that takes as input some
string, and outputs "yes" or "no". If there is an algorithm (say a
Turing machine, or a computer program with unbounded memory) which is
able to produce the correct answer for any input string of length
Failed to parse (<math_output_error>): n
in at most c \cdot n^k steps, where k and Failed to parse
(<math_output_error>): c are constants independent of the input
string, then we say that the problem can be solved in polynomial time
and we place it in the class P. Formally, P is defined as the set of
all languages which can be decided by a deterministic polynomial-time
Turing machine. That is,
P = {L:L = L(M) for some deterministic polynomial-time Turing machine
M}
where L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}
and a deterministic polynomial-time Turing machine is a deterministic
Turing machine M which satisfies the following two conditions:
1. M halts on all input w; and
2. there exists k \in N such that T_{M}(n)\in\; O(nk),
where T_{M}(n) = \max\{ t_{M}(w) : w\in\Sigma^{*}, \left|w\right| = n
\}
and tM(w) = number of steps M takes to halt on input w.
NP can be defined similarly using nondeterministic Turing machines
(the traditional way). However, a modern approach to define NP is to
use the concept of certificate and verifier. Formally, NP is defined
as the set of languages over a finite alphabet that have a verifier
that runs in polynomial time, where the notion of "verifier" is
defined as follows.
Let Failed to parse (<math_output_error>): L
be a language over a finite alphabet, S.
L\in\mathbf{NP} if, and only if, there exists a binary relation R
\subset\Sigma^{*}\times\Sigma^{*} and a positive integer k such that
the following two conditions are satisfied:
1. For all x\in\Sigma^{*}, x\in L \Leftrightarrow\exists y\in\Sigma^
{*} such that (x,y)\in R\; and \left|y\right|\in\;O(\left|x\right|^
{k}); and
2. the language L_{R} = \{ x\# y:(x,y)\in R\} over \Sigma\cup\{\#\}
is decidable by a Turing machine in polynomial time.
A Turing machine that decides LR is called a verifier for L and a y
such that (x,y)\in R is called a certificate of membership of x in L.
In general, a verifier does not have to be polynomial-time. However,
for L to be in NP, there must be a verifier that runs in polynomial
time. --MartinMichaelMusatov 07:18, 24 February 2009 (UTC)
[edit] NPC: NP-Complete
The class of decision problems such that (1) they're in NP and (2)
every problem in NP is reducible to them (under some notion of
reduction). In other words, the hardest problems in NP. Two notions of
reduction from problem A to problem B are usually considered:
1. Karp or many-one reductions. Here a polynomial-time algorithm is
given as input an instance of problem A, and must produce as output an
instance of problem B.
2. Turing reductions, in this context also called Cook reductions.
Here the algorithm for problem B can make arbitrarily many calls to an
oracle for problem A.
Some examples of NP-complete problems are discussed under the entry
for NP. The classic reference on NPC is [GJ79]. Unless P = NP, NPC
does not contain any sparse problems: that is, problems such that the
number of 'yes' instances of size n is upper-bounded by a polynomial
in n [Mah82]. A famous conjecture [BH77] asserts that all NP-complete
problems are polynomial-time isomorphic -- i.e. between any two
problems, there is a one-to-one and onto Karp reduction. If that's
true, the NP-complete problems could be interpreted as mere
"relabelings" of one another. NP-complete problems are p-superterse
unless P = NP [BKS95]. This means that, given k Boolean formulas
F1,...,Fk, if you can rule out even one of the 2k possibilities in
polynomial time (e.g., "if F1,...,Fk-1 are all unsatisfiable then Fk
is satisfiable"), then P = NP.
[BH08] H. Buhrman and J. Hitchcock. NP-Hard sets are exponentially
eense unless NP is contained in coNP/poly, Electronic Colloquium on
Computational Complexity, ECCC Report TR08-022, accepted on Mar 11,
2008. http://eccc.hpi-web.de/eccc-reports/2008/TR08-022/index.html
[Yap83] C. Yap. Some consequences of non-uniform conditions on uniform
classes, Theoretical Computer Science, (1983), 26, 287-300.
[GJ79] M. R. Garey and D. S. Johnson. Computers and Intractability: A
Guide to the Theory of NP-Completeness, Freeman, 1979.
[Mah82] S. R. Mahaney. Sparse complete sets for NP: Solution of a
conjecture by Berman and Hartmanis, Journal of Computer and System
Sciences 25:130-143, 1982.
[BH77] L. Berman and J. Hartmanis. On isomorphism and density of NP
and other complete sets, SIAM Journal on Computing 6:305-322, 1977.
[BKS95] R. Beigel, M. Kummer, and F. Stephan. Approximable sets,
Information and Computation 120(2):304-314, 1995.
http://www.cis.temple.edu/~beigel/papers/bks-queries2-ic.PS.gz.
.
- Prev by Date: Re: Mean and Stdev
- Next by Date: Re: RIEMAN HYPOTHESIS
- Previous by thread: NP: Nondeterministic Polynomial-Time
- Next by thread: --- --- --- Conditional solution
- Index(es):
Relevant Pages
|
