Re: NP-hard problems

On Thu, 27 Mar 2008 15:58:54 +0100, saneman <asdfsdf@xxxxxxx> wrote:

Timothy Murphy wrote:

saneman wrote:

As I understand a problem is said to be NP-Hard if there is no
polynomial time algorithm that can solve it.

But what if I have a logarithmic algorithm that solves the problem?
Logarithmic functions are not polynomial.

I wonder if you really have a "logarithmic algorithm"?
I imagine they are quite rare.

Comparing the first 2 elements is O(log n).

Remember that it is polynomial time in the _length_ of the input,
so if you are talking about integer input,
it is polynomial time in log n.

Its possible to find an element i lg n time (asymptotic notation) in a
red/black tree.

I don't think so.

A single comparison is O(log n), but you need O(log n) such
comparisons, hence the actual search time is O((log n)^2), not O(log
n).

quasi
.

Relevant Pages

  • 6P=NP: Proof: Nondeterministic Algorithm
    ... each time the algorithm is run the resulting guess may differ. ... be done in Oor polynomial time. ... verifies x if there exists a certificate y such ... Algorithm A verifies language L if for any string x Î ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... complicated algorithm works better (avoids backtracking entirely, ... indexed variable, assigning a value to a variable, or comparing two ... so, once you "big O" it, you end up with a running time of 1. ... in polynomial time. ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... complicated algorithm works better (avoids backtracking entirely, ... indexed variable, assigning a value to a variable, or comparing two ... When doing this calculation, you should use the symbol N ... in polynomial time. ...
    (sci.math)
  • Re: Aspiring highest-order programmer
    ... > that today's programmers repeat the mistakes of the past because their ... not the algorithm choosen to solve it. ... it means that there is no known polynomial time algorithm to ... algorithm to solve any NP-complete problem, ...
    (comp.programming)
  • Re: JSH: Nearly done
    ... my response to your "polynomial time" below.) ... algorithms really are, so I'll tell you: For a factoring algorithm to ... it doesn't hurt to use recursion in a "proof of concept" ...
    (sci.math)