5 ms·
Lowering the algorithmic upper bound for a core NP-complete problem is always extremely interesting. However, this is not necessarily related to improving runt
by mzl 3y ago
Lowering the algorithmic upper bound for a core NP-complete problem is always extremely interesting. However, this is not necessarily related to improving runtime for practical implementations solving the problem in question.
Solvers for mixed integer programming (MIP) use a lot of algorithms in conjunction with loads of heuristics. Building up the library of heuristics and strategies is a crucial part of why the improvement in MIP solvers have outpaced Moores law. From https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/602.f16/602miscfiles/UF_Entrepreneurship_19November2014.pdf https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6..., the improvements in hardware from 1990 to 2014 was 6500x. But the improvements to the software are responsible for 870000x performance improvement.
The referenced article may become another part of the puzzle in continuing performance improvements for MIP solvers, but it is not in any way a given.
- WhitneyLand 3y ago[flagged]
- eigenket 3y agoRun time, runtime and run-time are all commonly used for the thing you want to call run time. None are incorrect. https://www.collinsdictionary.com/dictionary/english/runtime https://www.collinsdictionary.com/dictionary/english/runtime
- WhitneyLand 3y agoInformally they are used interchangeably. However, their definitions are different. The subject here, is academic research involving algorithmic complexity. What papers do you know of that refer to algorithmic complexity and “runtime”? Context matters. It is incorrect in this context.
- eigenket 3y agoGoing on arXiv computer science and searching for the string "runtime" returns 6135 results, many of which seem use it in the sense we're talking about here. https://arxiv.org/search/cs?query=runtime&searchtype=all&abstracts=show&order=-announced_date_first&size=50 https://arxiv.org/search/cs?query=runtime&searchtype=all&abs... In any case Quanta Magazine is not a formal academic journal, and neither is hacker news. We're having an informal discussion about a popular science article.
- WhitneyLand 3y agoYour 6135 results are ignoring that there are two different usages. I said “run time” relates to algorithmic complexity. That’s one definition. The other definition is also valid in research, as it relates to environments. Like Java. The first result in your query is an example of the second definition. It is not an example showing these are interchangeable.
- eigenket 3y agoFine, I edited "most" in my previous comment to "many". There are still plenty of examples (even on the first page) where the "runtime" is used to mean algorithmic complexity https://arxiv.org/abs/2401.14645 https://arxiv.org/abs/2401.14645 https://arxiv.org/abs/2401.13770 https://arxiv.org/abs/2401.13770 https://arxiv.org/abs/2401.12253 https://arxiv.org/abs/2401.12253 https://arxiv.org/abs/2401.12205 https://arxiv.org/abs/2401.12205 https://arxiv.org/abs/2401.10856 https://arxiv.org/abs/2401.10856
- WhitneyLand 3y agoI’ll respond to what I think are the real points: Precision doesn’t matter in this case? I disagree. It was a dick move and pretentious to call it out? Maybe so, it was not my intent and I apologize if it was the case.
- eigenket 3y agoMy point is that I am a researcher (in quantum information theory) and I've published a couple of papers on quantum computing which talk about algorithmic complexity. In once case I've been told to by an editor to change run time to runtime, and in another case I've been told (by an editor at a different journal) to change run-time to run time. There isn't a fixed consistent usage, even in the academic literature. More importantly though it doesn't matter which you use, as long as its obvious what you're talking about.
- GaryNumanVevo 3y agoKeeping the HN tradition of "pedantry at all costs" alive, I applaud you
- vacuity 3y agoYou shouldn't be using a comma in that position! You could use a period or semicolon instead!!! How can an esteemed HNer not know basic punctuation?!
- dahart 3y agoIt seems like you’re confusing your favorite term of art for definitions. One listed valid definition of “runtime” is “the amount of time that a program takes to perform a task”, and as such it’s valid to use the word that way in any context. https://www.oxfordlearnersdictionaries.com/us/definition/english/runtime https://www.oxfordlearnersdictionaries.com/us/definition/eng... Also worth keeping in mind that usage defines what words mean. If a given usage is common, that makes it de-facto correct, and eventually the dictionary will catch up. This one reason why the dictionaries keep adding new definitions. Since you’re incorrect about the definitions, and since the meaning of the word runtime was correct in the top comment and understood by everyone reading, and never confused in this thread, the context does not matter here in this case. I’ve learned from a lot of experience being wrong that the problem with trying to police language is you’re almost never right. Words are beautifully fluid and have multiple and surprising meanings. It’s common for people to mistakenly think the meaning they know is the only meaning, and not be aware of the wider history and usage. So, speaking from experience in the role of English pedant, and getting rightly smacked down, be careful or you end up on the wrong side of your corrections.
- robertlagrant 3y agoNone is correct.
- deleted 3y ago[deleted]
- junon 3y agoWas #1 really worth mentioning...?
- hyperluz 3y agoFor me, it was, because it was informatve and I'm tired of imprecision, terms overloading, ambiguity and indirectnesses. Take a look at the Rust's crate.io mess, for example, where people misuse "crate" all the time.
- whyever 3y agoIsn't this a stylistic choice? For example, some style guides would suggest to use "run time", but also "run-time error".
- deleted 3y ago[deleted]
- mzl 3y agoThe original paper (https://arxiv.org/pdf/2303.14605.pdf https://arxiv.org/pdf/2303.14605.pdf) that the linked article reports on is a theoretical algorithms paper, and does not contain any references to actual solvers or implementations. For practical cases it is not that important what the worst-case complexity is, but rather what the expected complexity is of solving problems that occur in practice.
- ur-whale 3y ago> Sorry to be pedantic As always, a guaranteed way to make friends.
- chuckSu 3y ago[dead]
- iouwhldkfjgklj 3y ago[flagged]
- pxx 3y agoIf you're going to be pedantic, you need to at least be correct. There is no such thing as an "NP class algorithm". There are, instead, languages that are NP-complete, for which we hypothesize that there are no polynomial-time algorithms for, because that would imply P=NP. It's a further unproven hypothesis that NP-complete languages have no sub-exponential time algorithms (the "exponential time hypothesis").
- deleted 3y ago[deleted]