is quitting smoking np hard?

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > is quitting smoking np hard?

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

Cybernetic Vermin posted:

people go something like:

f(x,y) \in O(g(x,y)) iff there exists c and m such that f(x,y) < m*g(x) for all x>c and y>c

issue is that this program is then in O(x+y):
code:
int f(int x, int y) {
    if(x==0) {
        return fexp(y,y);
    }
    else {
        return x+y;
    }
}
since picking c>0 immediately makes the exponentiation disappear.

yeah i mean weird-rear end non-monotonic cost functions certainly do give this loosy-goosy intuitive analytical tool some trouble, you got that right

# ¿ Aug 17, 2023 21:01

Adbot: ADBOT LOVES YOU

# ¿ May 9, 2024 09:12

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

Cybernetic Vermin posted:

it is not a loosy-goosy intuitive tool though, it is just abused a lot.

look, if you�re studying it formally for some mysterious reason then sure, you might as well find a definition that doesn�t have that specific flaw. but who cares, it is not actually mathematically interesting, it is a communicative tool for establishing broad categories of asymptotic cost. usually people don�t even bother to define what costs they�re measuring, just some nebulous idea of �steps�, and it�s just as communicatively useful.

if precise counts for some cost are actually important then you should probably give an actual function for it instead of just a theta class

there are all sorts of bizarre non-monotonic cost functions that are not summarized well by a theta class, like a function that takes trillions of steps for n <= 5 but then f(n) = 2n otherwise. but usually the assumption is that the inputs to this cost function are various measurements of the size of the input, and why would smaller inputs ever uniformly be more expensive than larger ones

# ¿ Aug 17, 2023 21:37

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

echinopsis posted:

yeah this is a thread about objectively the coolest thing you can do and it loving changed up i to god drat nerd-o-rama

look i can�t let this person get away with being right in a way i disagree with

# ¿ Aug 17, 2023 21:38

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

Cybernetic Vermin posted:

i and just about every single person in existence doing algorithmics work use big-o, intend a precise meaning, and if we're abandoning the meaning would need to invent new terminology for what was previously intended.

i�m not trying to say it�s useless and should be abandoned, i�m saying that you�re just loosely bounding the overall costs as an important part of describing the algorithm, and having holes of a sort in the formal definition that would only matter for implausible functions doesn�t seem like it meaningfully damages that goal

i mean sure, if someone did have an algorithm with a cost function like that, and they published it with a big-O description that completely elided that complexity because of that flaw in the formal definition, i guess someone else who trusted that big-O could publish an algorithm derived from it and do a completely incorrect analysis of their own big-O. that would be pretty upsetting for sure

rjmccall fucked around with this message at 00:00 on Aug 18, 2023

# ¿ Aug 17, 2023 23:55

rjmccall: Sep 7, 2007; no worries friend; Fun Shoe

this is yospos, algorithms are never off topic

# ¿ Aug 19, 2023 03:42

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > is quitting smoking np hard?