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: simple and beauty strategy
    ... The relation between the complexity classes P and NP is studied in ... positive solutions can be verified in polynomial time given the right ... the NP-complete problems are the "toughest" ... that every algorithm which decides the truth of Presburger statements ...
    (rec.gambling.lottery)
  • Please Help
    ... Instead of a deterministic Turing machine, ... The theoretical notion of "quick" used here is that of an algorithm ... in polynomial time, so this problem is in '''NP'''. ...
    (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 ... so, once you "big O" it, you end up with a running time of 1. ... in polynomial time. ...
    (sci.math)