Re: another proof that p is not np

cafeinst_at_msn.com
Date: 12/08/04 

Date: 8 Dec 2004 09:57:13 -0800

Delete Fruit wrote:
> http://arxiv.org/abs/cs/0310060
>
> I have glanced at your paper- trying to understand it:)

Thank you. I just read your post now, which is why I did not respond
when you wrote it. I'll try to answer your questions.

>
> "We use induction on n: We shall leave it to the reader to find a
large
> enough N to verify the basis step."
>
> Please find N.

I think that one could argue the basis step for N=4 in some reasonable
model of computation. The model of computation would assume that
sorting X elements takes the same amount of time as checking whether
one of the X elements is equal to a given number. Even though this may
not be reasonable in real life, it makes the argument easier to
understand and does not affect the validity of the argument.

You should know that the algorithm in my paper is the fastest-known
exact algorithm for solving subset-sum, and it was discovered in the
early 1970's. About 30 years have gone by without an improvement in its
running-time. This in of itself is evidence that it is the fastest
exact algorithm for solving subset-sum, so the idea of trying to prove
that p is not np by proving that this algorithm is the best algorithm
for solving subset-sum is certainly an idea worth considering. As far
as I know, one cannot say anything like this for the more popular
np-complete problems like SAT.

>
> "When this improved strategy is implemented, the algorithm not only
> solves each subproblem in the fastest way possible by the induction
> hypothesis, but also the algorithm makes use of any information that
is
> obtained from solving any one of the subproblems to save time solving

> the other subproblem whenever it is possible to do such."
>
> How are you sure that the algorithm makes use of *all* information in

> the *best* way possible?

That is really the intuitive part of my argument. The best way to
understand where I am coming from is to think carefully about how
algorithm A solves both of the subproblems and how the information
obtained from solving one of the subproblems is used to solve the other
subproblem. If one assumes the induction hypothesis, one can see that
it is impossible to beat algorithm A on problems of size n+1, since the
algorithm optimizes the use of information obtained from solving both
subproblems.

>
> Also, what stops me from using your argument for any algorithm which
> solves an NP-complete problem and is amenable to induction?

The type of argument in my paper would not work on any algorithm which
solves an NP-complete problem, only the algorithms that are optimal and
amenable to induction. It may be that the subset-sum problem is the
only problem which permits such an argument; I don't know for certain.
The concept in my paper is to break the original problem down into two
independent subproblems, and find an algorithm which solves each of the
subproblems in the best way possible using an induction hypothesis and
make optimal use of information obtained in the process of solving each
of the subproblems to save time solving the other subproblem.

>
> sundeep
>
> ps: I would appreciate a reply which is not:
> "The argument in this note is put forward in a purely intuitive
> spirit and should not be interpreted as a rigorous proof; however,
the
> author is by no means claiming that a rigorous version of the
argument
> presented here is impossible. And the author welcomes and challenges
> anyone to produce a rigorous version."

I do not have a rigorous argument. I am waiting for someone else who
can do a better job at communicating than myself to finish what I
started. If anyone can do this, then they will have solved the p vs. np
problem and they will have my congratulations.

Craig

Relevant Pages

  • Re: Question: the modern/state-of-the-art P?=NP research
    ... The strategy is to prove that the fastest known algorithm that solves ... the subset-sum problem, found in the paper Woeginger, G.J., ``Exact ... I make the observation that solving a problem ... calculated and used to solve both subproblems (in order to save time, ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... I don't say that giving weigths is disabled in instance. ... instance without weights but only with binary encoded n then it had ... Then if algorithm checks in first step are weigths ... But the counterexample's subproblems ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... Held-Karp is the fastest possible algorithm to calculate the subproblems ... Held-Karp algorithm in speed. ... algorithms which can *beat* the Held-Karp algorithm in speed. ... who doesn't love puppies?], is ...
    (comp.theory)
  • Re: An easy way to prove P != NP
    ... So you only talk about lower bound for algorithm not problem. ... faster worst-case asymptotic running-time in the RAM ... Programming Principle - Suppose that problem P is to find the minimum value ... algorithm A solves each of these subproblems in the minimum running-time ...
    (comp.theory)
  • Re: Recursion problem - Graph theory - Algorithm needed
    ... )> I pose a question here concerning what I think is a classic computer ... but I don't know of an algorithm for solving it. ... here are 15 square tiles arranged in a 4x4 grid, ...
    (comp.programming)