### Comment on

 Need Help??
NP-completeness is a property of an algorithm. It implies that no algorithm is known to solve the problem in polynomial time.
This means that if you increase the length of the input for the problem, the execution time will increase exponentially. (Of course there are input cases which are polynomial, but many of interest are not). Essentially, it means that brute force is the only known method to tackle the problem exactly.

I think that this may be a little misleading. Right now (as 6 years ago), NP-completeness of a problem means that no polynomial-time algorithm is known, but that statement may eventually become false *. Maybe it's better to say “Computer scientists believe that, if a problem is NP-complete, then there is no polynomial-time algorithm to solve it”?

Also, I'm not sure that it's fair to say that NP-completeness of a problem means that the time-complexity of the problem grows exponentially in the input. Again, we think that NP-completeness correlates with exponential time-complexity, but that could change *. For that matter, can't NP-complete problems have super-exponential complexity (like 2^(n^2))—or are you using ‘exponential’ in the generic sense of ‘faster-growing than polynomial’?

* Although we all know that it won't really. :-)

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
 [Corion]: marto: I believe nowadays, at least window.opener should not be set anymore (except maybe within the same domain) [Corion]: But I wouldn't really know as I don't use iexplore much (except at \$work) and mostly surf with JS disabled (except at \$work :) ) [marto]: yeah, this is at work, where some intranet app launches links via window.open. When users close the intranet page so that only the new JS opened windows exist, clicking URLs in an email (or whatever) don't open [Corion]: marto: It somewhat makes sense that the reduced popup window doesn't get new URLs, but it makes less sense that no new browser window opens :) [marto]: Corion, yeah, why no new browser window opens is currently beyond my understanding

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (7)
As of 2018-03-21 11:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (267 votes). Check out past polls.

Notices?