is quitting smoking np hard?

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

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

allan carr's book was talked about on this american life a few weeks ago and it doesn't come out looking great, mostly incurious pseudoscience that happens to align with working with people sometimes

they interview the guy who runs the Allan Carr foundation and are all, "but look, you can measure scientifically that nicotine has an effect on the body in contrast to what the book (and the guy above who's all "nicotine highs are just oxygen deprivation") tells you" and the Allan Carr guy gets super defensive and says "well the studies are wrong and I believe something different", to the point where weeks after the interview the guy is calling the TAL host and leaving weird messages on his voicemail about "why would you want to defend smoking" as if NPR is in the pockets of Big Pharma or something :rolleyes:

but to the OP's question: I can validate in polynomial time whether you have smoked in the the last `n` days so it is not NP-hard

Dijkstracula fucked around with this message at 15:34 on Aug 17, 2023

# ¿ Aug 17, 2023 15:17

Adbot: ADBOT LOVES YOU

# ¿ May 9, 2024 08:56

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

OldAlias posted:

lol that�s weird. like why lie it�s not like it�s hard to make an argument against smoking, lying about basic facts is a good way to get ppl to not trust anything you�re saying

the weirdest thing was that it wasn't even a lie in the sense that the other person didn't seem to know or care; the Allan Carr Institute guy treated the easy way method more like blind faith than anything else and thought the notion that a bit of empiricism and neurobiology things might inform a (n even) better way to quit smoking absurd

akadajet posted:

tech interviewers really like the big o though, so it's good to have a handle on for that alone. if interviewers started talking about p or np or whatever I'd laugh at them

yeah, the only time in an interview where I benefitted from knowing about complexity classes was (of course) in a Google interview when I was given a slightly obfuscated traveling salesman problem to which the interviewer just wanted to hear "in the next 45 minutes we're not going to do much better than brute-forcing all routes so I'll just do that"

# ¿ Aug 17, 2023 15:57

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

just count the depth of your nested loops, bingo bango

# ¿ Aug 17, 2023 16:00

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

Cybernetic Vermin posted:

plus the folklore definitions of big-o over multiple variables is straight up incorrect.

how is it incorrect

# ¿ Aug 17, 2023 16:04

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

in hbag's defence, if I only ever saw the formal definition of asymptotic complexity (the whole "if for all n > n0 there exists some k s.t. f(n) <= k*g(n) then f(n) = O(g(n))" or whatever it is) then it wouldn't make a lick of sense to me too

the good news is that in the real world those constant factors actually matter, so in practice you're not significantly more wrong if you play it fast and loose with big-o

# ¿ Aug 17, 2023 16:08

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

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" :q:

# ¿ Aug 17, 2023 16:18

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

someone itt seems to be getting somewhat riled up, have you considered ingesting a substance that binds to the Alpha-9 and Alpha-10 nAChR receptors, inducing a dopamine release and calming effect

Dijkstracula fucked around with this message at 16:35 on Aug 17, 2023

# ¿ Aug 17, 2023 16:29

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

Cybernetic Vermin posted:

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.

if grad school has taught me anything, it's that I shouldn't be surprised when a very smart person screws up something nominally simple

# ¿ Aug 17, 2023 16:30

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

if your time complexity is too big, use a hash table instead

if your smoking addition is too strong, switch to hash instead

# ¿ Aug 17, 2023 18:58

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

hbag posted:

if i need to understand this to get a computer touching job i might as well just put in my application at mcdonalds now

Dijkstracula posted:

just count the depth of your nested loops, bingo bango

# ¿ Aug 17, 2023 20:46

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

hbag posted:

so id end up with, for example, O(3) instead of "O(n log n) or whatever"
that doesnt seem right

oh boy you really didn�t learn this huh

no, if you had three nested loops, say:

code:

for i = 0..n:
  for j = 0..n:
    for k = 0..n:
      // something involving i, j, k

how many times do you execute the line with the comment on it! n times for each value of j, to which there are n, and that happens n times for each value of i, so it�d be n*n*n and if the body of the inner loop has constant time complexity, then you�d have O(n^3) * O(1) = O(n^3)

with some similar reasoning you can show the same thing with other bounds on the loop variables (like e.g. j from 0..i and k from 0..j)

by contrast you often see log terms when you split work into two at each iteration, like in binary search ( O(log n) since you are subdividing the space by half each time) or many search algorithms (O(n log n) because you also divide the search space by 2 but do O(n) work each time you do it)

# ¿ Aug 17, 2023 20:57

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

hbag posted:

...uh-huh

try it yourself: consider a single nested loop:

code:

for i = 0..n:
  for j = 0..i:
    // �

what are the values of i and j that could be in the loop? (0,0),(1,0),(1,1),(2,0)..(n-1, (n-1)-1). how many pairs of numbers are there, �roughly�? well, roughly the first element runs from 0 to n, as does the second one, so the number of total pairs feels like it�s quadratic in n, so a guess would be that this has time complexity O(n^2). and it does! (convince yourself that by a similar reasoning, 0+1+2+..n which is (n * (n+1))/2, if you expand it out and throw away the constant factor, also gives you n^2)

its not impossible or obtuse if you keep it high-level like this, it just takes practice to see the common patterns

# ¿ Aug 17, 2023 21:07

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

well if you�re only in high school I don�t know when you would have learned any of this, I thought from your past posts you were graduating uni or something

also I�ll say it again, you don�t get stuff by reading my bad posts that I�m typing on my phone whilst I�m pooping, you get stuff by actually playing around with the concepts yourself

# ¿ Aug 17, 2023 21:11

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

well then you�ll have plenty of time to get a sense of rough and ready complexity analysis before someone makes you do it in a whiteboard interview

# ¿ Aug 17, 2023 21:20

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

I do love the smell of pipe smoke tho

# ¿ Aug 17, 2023 21:48

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

well-read undead posted:

for the minority of roles where writing high performance algorithms is a core requirement, maybe it's a thing

if anything this is the situation where it isn�t a thing; if you�re doing something where you�re twiddling bits to eke out a 5% improvement in a tensor computation or whatever, that constant factor would just disappear in the complexity analysis

# ¿ Aug 17, 2023 22:30

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

rotor posted:

Smoking is very bad for you but it does make you look cool and im tired of people pretending it doesnt

my local pub had Cool Hand Luke on the TVs the other night and it inspired me to conclude that if you want to look cool but not smoke you can also try to eat 200 eggs

# ¿ Aug 18, 2023 14:16

Adbot: ADBOT LOVES YOU

# ¿ May 9, 2024 08:56

Dijkstracula: Mar 18, 2003; You can't spell 'vector field' without me, Professor!

echinopsis posted:

how does a person join the forums in 2022 unless it�s a re-reg

gonna need hbag to weigh in on this one

# ¿ Aug 19, 2023 00:46

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