is quitting smoking np hard?

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

Cybernetic Vermin: Apr 18, 2005

OldAlias posted:

big O is rly easy? idk what�s not to get

nah. researchers that should know better gently caress up often, e.g. writing O(2^n) when they mean 2^(O(n)), writing O when they mean Omega, plus the folklore definitions of big-o over multiple variables is straight up incorrect.

# ¿ Aug 17, 2023 16:02

Adbot: ADBOT LOVES YOU

# ¿ May 9, 2024 07:47

Cybernetic Vermin: Apr 18, 2005

Dijkstracula posted:

how is it incorrect

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.

Cybernetic Vermin fucked around with this message at 16:30 on Aug 17, 2023

# ¿ Aug 17, 2023 16:09

Cybernetic Vermin: Apr 18, 2005

Dijkstracula posted:

ah, I see what you mean by multiple variables now

yeah honestly I don't know how to reason formally about that function if I'm being honest, but that's another advantage to having gone to a second-rate uni and being sloppy with the technique I guess - I can stare at it for a bit and say "well, seems like if you curried the function of two variables into two functions of one argument and took the max complexity of both, that gets you maybe less wrong"

yeah, i think the correct way to define it is along those lines, with a strategic 'max' somewhere. though tbh i think the entire 'c' bit is a mistake, as it only really matters to bound arguments away from zero.

not a very deep issue in practice at any rate, but the fact that tons of books and papers by very clever people fucks this up does illustrate that it is not *that* simple.

# ¿ Aug 17, 2023 16:26

Cybernetic Vermin: Apr 18, 2005

rjmccall posted:

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

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

# ¿ Aug 17, 2023 21:08

Cybernetic Vermin: Apr 18, 2005

rjmccall posted:

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.

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.

rjmccall posted:

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

this is nonsense, the reason it is used is that it is often extremely difficult to establish a precise function, and for algorithmics in particular it would be tied to then contrived assumptions (e.g. precise bit layouts of inputs, exact computational model details). if you do like finite automata state complexity work you do try to escape to precise bounds, but even in that simple case there is a lot of work expended accounting for the smallest details (e.g. restate the proof for the case where you are permitted more than one initial state).

and that is for big-o's, thetas is extremely optimistic, there's so little in the world we have lower bounds for.

rjmccall posted:

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

for a single variable it is fine is the thing, there's no real need for monotonicity. the easy way by setting the cutoff c=6 to get rid of n<=5, but also you can just set the linear factor m=max {f(1), ..., f(5)} and c=1 whenenever only a finite number of elements exceed the intended function.

the entire point of the original point is that it is a small technical niggle that a lot of people and places missed, that as you go to multivariate functions you need to actually make a monotonicity assumption of some kind (i.e. insert a suitable 'max'), and it is not necessarily that obvious how to do it even, at least if you want to cover the reals (which, granted, for algorithmics you usually would not care about).

# ¿ Aug 17, 2023 22:06

Cybernetic Vermin: Apr 18, 2005

yeah, i am absolutely not trying to argue that i am expressing something of universal interest here

mostly wanted to comment as saying "x is easy" is misleading (and possibly unnecessarily disheartening for those that then try to read the wikipedia or so) when really its "you can blag your way through x easily enough"

# ¿ Aug 17, 2023 22:25

Cybernetic Vermin: Apr 18, 2005

well-read undead posted:

i�ve never been probed in my account�s relatively short lifespan, and i�m sure calling attention to that fact will do nothing to change it

imo the latter half of this post is an opinion

# ¿ Aug 18, 2023 23:15

Cybernetic Vermin: Apr 18, 2005

good work getting the bad joke people

# ¿ Aug 18, 2023 23:30

Adbot: ADBOT LOVES YOU

# ¿ May 9, 2024 07:47

Cybernetic Vermin: Apr 18, 2005

well-read undead posted:

lol similar to hbag, i�ve known about something awful for like 20 years, i was just never tempted to register

if i hadn�t somewhat randomly ended up reading a yospos thread around when elon musk bought twitter i still wouldn�t have

please at least make up a better reason

# ¿ Aug 19, 2023 01:49

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