Is P=NP? Thought process approach.
Ramasamy C
Got a small view about the celebrated problem. Need
clarifications on this. If completely wrong, please do tell me where
its wrong.
IS P=NP?
Given any problem, humans tend to think over the problem and
find the solution over a span of few days or months or even years. The
thought process can be considered to be an NP complete problem (Though
we might actually making some assumptions inherently). Any problem is
bound either to have or not to have a solution. (Here is where we make
a critical assumption violating Godel's incompleteness). If that is the
case, then, this assumption says P=NP has some solution. Given any
problem, we tend to find the solution in the thought space or the
logical space of our mind and move to the problem's solution in
different paths whichever is logical and takes us to the solution. This
is nothing but the traversal in the solution graph of the problem
presented. Since we do not know before hand which path would lead us to
the solution, we face with no better method other than trying out all
possible methods. (This is done by the mind inherently by finding the
best method of attack from the description of the problem). Hence,
thinking and arriving the solution of the presented problem is an NP
complete one. Once the problem's solution is formulated, its always
easier to read through the solution and hence find its correct! (The
'P' part of thought process). We're trying to find the solution of the
P=NP by using a process which is inherently NP complete. If P=NP turns
out to be true, which means, given a problem, its solution can be
recovered through some form of algorithm without actually trying out
all methods, we could rewrite the solution for FLT and even generalized
Catalan's problem. Here is where Godel's incompleteness comes into
help. What if the problem cannot be determined of its solvability? In
this case we'll not have the solution and hence P will not be equal to
NP.
Thanks
Ramasamy C
Sed
In article <1131452990.9...@f14g2000cwb.googlegroups.com>,
Ramasamy C wrote:
> [...] The
> thought process can be considered to be an NP complete problem
Prove it, using Turing machines, where P and NP classes are defined.
> [...] Since we do not know before hand which path would lead us to
> the solution, we face with no better method other than trying out all
> possible methods.
Do you have some scientific experiments' references that tend to
give credits to this hypothesis?
> Thanks
> Ramasamy C
Cédric.
--
char*t= "u]Gd\\wa[nc[eHEdBQbhb`hgHWRLSbYfaYeHAIPQbhb`heHQINwihnkh";int
main(void) {int i=0,c;for(;i<330;c>>=1){if(i++%6==0)c=*t++;printf(i%66
?"%c":"%c\n",c&1?'|':' ');}return printf("is a nice little thing\n");}
Ramasamy C
> [...] Since we do not know before hand which path would lead us to
> the solution, we face with no better method [...]
Regarding the above, considering all problems to be
solvable/unsolvable, we get a graph of solutions that originate from
the problem and would end up in the solution. I think the problems like
prime numbers are infinite, has many solutions (though some are
similar). Mind tend to push towards the solution through the learning
done before and this helps to reach the solution by ignoring
unnecessary paths towards the solution. But this is not the case
always. For example, the celebrated problem of FLT had so many flawed
proofs! At some point when we hit on a brick wall while travelling
through a maze of solution to find a way out, we have to rewind few
steps back and find another approach. This is clearly nothing but
trying out all possible methods, except that one cannot try all methods
due to practical constraints of time.
This is a meta-mathematical argument rather than a concrete theoritical
one. This displays a "strange loop" as said by "Douglas R.Hofstadter".
Thanks once again,
Ramasamy C
Ben Rudiak-Gould
> We're trying to find the solution of the
> P=NP by using a process which is inherently NP complete.
A "process" can't be NP complete. Yes, the problem of determining whether a
given theorem has a proof shorter than a given length is in NP. So if P=NP
then we could efficiently find the shortest proof of FLT, and probably
settle many outstanding mathematical conjectures by computer. This is a good
reason to believe that P != NP.
But I fail to see the connection to the process of doing mathematics. The
fact that a given decision problem is NP-complete, or for that matter
undecidable, has no impact on the solutions of particular instances. It's
well known that FLT can be formulated as an instance of the halting problem,
but that doesn't mean that the process by which it was proven is a special
case of a general process for solving any instance of the halting problem.
The proof of FLT has nothing to do with the halting problem.
-- Ben
Jaisingh Solanki
Certain important points:
Problem X is said to be in NP if there exist a polytime verifier V which
takes a general instance I of X and some witness W (may depend on I),
and whether W is a correct witness of I or not. And the crucial thing is
that W have to be polynomially bounded by I. And in your case you are
not assuming any bound on W (i.e. length of mathematical proof).
So the problem which you have defined (even if we assume that it can be
formulated in terms of trung machines) cannot be in NP. Because we can
have arbitrarly long proof of small mathematical problem.
Jaisingh Solanki
Ramasamy C
regarding any problem in case of generalizations as well as reduction
to particular instances. Also it is not very clear when does a problem
reaches its upper/lower bound in its generality/reduction. Another
point, the instances of the problem may not be related to each other in
simple terms though the generalised one could actually satisfy all
instances. An example is FLT. I need help in locating pointers
regarding formulation of FLT as halting problem.
Jaisingh, the existance of verifier can be confirmed in the thought
process by the following: The verification of the correctness of the
solution is bounded by P time since it doesnt take much effort as
solution proposal when compared to solution verfication. Even to very
long and complex solutions, it can be understood in relatively less
time. Though we can have long proofs for smaller mathematical problems,
finding a proof for a problem bounded by a length L, as Ben said is NP
complete.
Thanks,
Ramasamy C
Jaisingh Solanki
Yes we might check things in polytime. But your witness (in this case it
is length of the proof) have to be bounded by instance size (in this
case any problem). Then only the "problem" is in NP. Otherwise it is not
in NP. You can still have long proof of the problem. But if your witness
is not bounded by polytime then it is not in NP.
Lets take an example,
Problem I: Input is u,v and w (three natural number) and problem is to
check if there exist natural number x , y and z such that
x^u + y^v = z^w
Now I can give the witness to be (x=a,y=b,z=c) and my verifier just
check whether a,b,c satisfy the equation or not.
Can we say that problem is in NP ? Answer is no. Because a,b,c can be
arbitrarly long to satisfy the equation or there may not be any solution.
And proof of the fact that there is no solution can be arbitrarly long.
So just because we have fast verifier is not enough for problem to be in
NP. The number of witeness should be bounded by polynomial. And then only
you can have non-deterministic polynomial algorithm. Try to think of
situation where number of witness are infinite and then try to give
non-deterministic polytime algorithm (assume that you have constant time
verifier)
Ramasamy C
clarification Jaisingh.
jeffrey_...@yahoo.com
I think you mean that the length of the witness must be bounded
by a polynomial in the size of the input, not the number of
witnesses. Correct?
Jaisingh Solanki
Yes you are right. length of witness should be bounded by polynomial.
of course if we have number of witnesses bounded by polynomial then size
of witness will be bounded by polynomial. but other way round is not
true.