Re:Ford and Fulkerson
on
Does P = NP?
·
· Score: 1
You can find a description of their algorithm formaximum flow in a network (which
presumably is what the paper is about, since its title is Flows in Networks) in basically
any algorithms book. Ex. Cormen Leiserson Rivest, Introduction to Algorithms.
Re:NP Non-deterministic Polynomial
on
Does P = NP?
·
· Score: 1
The problem is clearly NP-complete, since it is
basically the same as the graph-coloring problem,
which is a well-known NP-complete problem.
There is one part of the review which doesn't make much sense
No, it's your post which doesn't make much sense.
A big part of this is simply wrong.
No, it's not.
Problems are NP-complete if it is proven that there is no algorithm which solves it in polynomial time.
No. A problem is NP complete if it is in NP (i.e it is an decision problem whose solution can be verified in polynomial time) and if every other problem in NP reduces to it. It is believed that there is no polynomial time algorithms for NP complete problem, but this has not been proved.
A problem is NP hard is every problem in NP reduces to it (i.e it need not necessarily be in NP)
If no literature is found, showing that the problem is NP-complete will take skills on highly advanced levels.
I'm not sure what you mean by "highly advanced". We teach it to second year undergraduate CS-students.
My (limited) experience with real-life examples is that they are either trivial or quite difficult to prove NP-complete.
The complexity of factoring an n-bit number under the NFS as you point out, is order of exp( (ln(n))^(1/3) * (ln(ln(n)) ^(2/3))
As someone pointed out, if this were true, factoring would be possible in subpolynomial time. The number n in the above should be the number being factored, not the number of bits.
Solving the DL problem would also solve the factoring problem, but not the other way around
As far as I know, this has not been proven (if you know otherwise, please provide a reference). However, in practice advances in factoring seems to leads to advances in discrete logarithms and vice versa.
Huh? There is not "two calling conventions" in ML. There is one calling convention, function followed by argument. Of course, the function can be any function-valued expression.
In the case on an uncurried function, the argument is a tuple. This is no different from using any other datastructure as an argument. I.e conceptually there is no difference between
f (x,y) and f (Leaf x)
Of course, the One True Programming Language is not ML, but Haskell.:-)
Slashdot Mirror
You can find a description of their algorithm formaximum flow in a network (which
presumably is what the paper is about, since its title is Flows in Networks) in basically
any algorithms book. Ex. Cormen Leiserson Rivest, Introduction to Algorithms.
The problem is clearly NP-complete, since it is
basically the same as the graph-coloring problem,
which is a well-known NP-complete problem.
No, it's your post which doesn't make much sense.
A big part of this is simply wrong.
No, it's not.
Problems are NP-complete if it is proven that there is no algorithm which solves it in polynomial time.
No. A problem is NP complete if it is in NP (i.e it is an decision problem whose solution can be verified in polynomial time) and if every other problem in NP reduces to it. It is believed that there is no polynomial time algorithms for NP complete problem, but this has not been proved.
A problem is NP hard is every problem in NP reduces to it (i.e it need not necessarily be in NP)
If no literature is found, showing that the problem is NP-complete will take skills on highly advanced levels.
I'm not sure what you mean by "highly advanced". We teach it to second year undergraduate CS-students.
My (limited) experience with real-life examples is that they are either trivial or quite difficult to prove NP-complete.
As someone pointed out, if this were true, factoring would be possible in subpolynomial time. The number n in the above should be the number being factored, not the number of bits.
Yes, you are missing that n^c only is polynomial
when n is the number of bits. Here, n is the
number being factored, so the number of bits is
log n
As far as I know, this has not been proven (if you know otherwise, please provide a reference). However, in practice advances in factoring seems to leads to advances in discrete logarithms and vice versa.
Well, factoring primes is easy. :-) However, factoring other numbers into primes (which is probably what you meant), does not require exponential time.
Huh? There is not "two calling conventions" in ML. There is one calling convention,
:-)
function followed by argument. Of course, the function can be any function-valued expression.
In the case on an uncurried function, the argument is a tuple. This is no different from using any
other datastructure as an argument. I.e conceptually there is no difference between
f (x,y)
and
f (Leaf x)
Of course, the One True Programming Language is not ML, but Haskell.