1.5M ratings
277k ratings

See, that’s what the app is perfect for.

Sounds perfect Wahhhh, I don’t wanna
ilzolende

ilzolende:

shieldfoss:

wirehead-wannabe:

the-grey-tribe:

evolution-is-just-a-theorem:

mindblowingscience:

A 25-year-old student has just come up with a way to fight drug-resistant superbugs without antibiotics.

The new approach has so far only been tested in the lab and on mice, but it could offer a potential solution to antibiotic resistance, which is now getting so bad that the United Nations recently declared it a “fundamental threat” to global health.

Antibiotic-resistant bacteria already kill around 700,000 people each year, but a recent study suggests that number could rise to around 10 million by 2050.

In addition to common hospital superbug, methicillin-resistant Staphylococcus aureus (MRSA), scientists are now also concerned that gonorrhoea is about tobecome resistant to all remaining drugs.

But Shu Lam, a 25-year-old PhD student at the University of Melbourne in Australia, has developed a star-shaped polymer that can kill six different superbug strains without antibiotics, simply by ripping apart their cell walls.

“We’ve discovered that [the polymers] actually target the bacteria and kill it in multiple ways,” Lam told Nicola Smith from The Telegraph. “One method is by physically disrupting or breaking apart the cell wall of the bacteria. This creates a lot of stress on the bacteria and causes it to start killing itself.”

The research has been published in Nature Microbiology, and according to Smith, it’s already being hailed by scientists in the field as “a breakthrough that could change the face of modern medicine”.

Before we get too carried away, it’s still very early days. So far, Lam has only tested her star-shaped polymers on six strains of drug-resistant bacteria in the lab, and on one superbug in live mice.

But in all experiments, they’ve been able to kill their targeted bacteria - and generation after generation don’t seem to develop resistance to the polymers.

Continue Reading.

Actual paper here. Also it’s behind a paywall, so a friendly reminder that SciHub exists.

Also as far as I can tell this is not one of those popular science articles that is obviously bullshit as soon as you read the abstract.

Wouldn’t it kill human cells too, outside of a Petri dish? Can you tell me why it didn’t kill the mice?

They specifically mention cell walls, which human cells don’t have. Both gram positive and gram negative bacteria do have cell walls, but without reading the actual paper I don’t know whether it would affect one type more than the other.

Wait human cells don’t have walls?

Mind blown I tell you.

We have cell membranes, which are thinner and less rigid. (IIRC)

All cells have membranes (actually gram negative bacteria have a nested pair of membranes) but not all cells have cell walls.

A cell membrane is made of two layers of lipids, their hydrophilic heads pointing outward towards the solution and their hydrophilic tails pointing inwards, each layer towards the other. Such a membrane is permeable to water but impermeable to most solvents (except at special channels regulated in various ways).

Many cells exists in environments that contain much less solvents than the cytoplasm of the cell. This drives water inside the cell (if water flowed into the cell, the cytoplasm would become more diluted bringing the system closer to thermodynamic equilibrium). If water was allowed to flow into the cell unchecked, the cell would eventually burst, a process known as osmolysis.

Different cells deal with this differently. 

Bacteria, plants, fungi and some protists have cell walls which are strong enough to withhold the osmotic pressure from inside the cell and prevent it from bursting. In fact, the mechanism by which penicillin and many other antibiotics work is exactly disrupting the cell wall and thereby causing osmolysis. These cell walls serve the same basic function but are very different between kingdoms: bacterial cell walls are made of peptidoglycan (a certain cross-breed between proteins and polysaccharides), plant cell walls are made of cellulose (a polysaccharide) and fungal cell walls are made of chitin (a different polysaccharide).

Protozoa (like the Amoeba) deal with this by continuously pumping water out of the cell, using special organelles called vacuoles. Vacuoles are basically membrane bubbles inside the cell that merge with the outer membrane and push out the contained water, subsequently reforming again.

To the best of my understanding, animal cells simply don’t have this problem since they exist in environments that are themselves solutions of equal osmotic pressure (i.e. equally rich).

ilzolende Source: sciencealert.com biology
jadagul

diffractor asked:

Many NP problems can be solved in most practical cases, like 3SAT. Just how much of the complexity hierarchy has "eh, good enough" solutions given current SAT algorithms? #P can be approximated. Intuitively I'd expect coNP problems to still be tricky, as it seems harder to show that SAT is unsolvable than to find a solution on typical instances. Any other examples of hard problems that suddenly become doable w SAT solvers, or NP/coNP/whatever problems where SAT solvers don't help much?

antisquark answered:

First, no, 3SAT cannot be solved in “most practical cases.” That is, I don’t know any practical use for 3SAT except reducing other problems in NP to 3SAT. So I don’t know how to interpret “3SAT can be solved in most practical cases” except as “all problems in NP can be solved in most practical cases.” The latter is definitely false, otherwise all of cryptography wouldn’t work, not to mention enormous advances we would have in automated engineering, mathematical proof search, synthetic biology and whatnot.

NP and coNP are both classes of decision problems, so being able to solve problems in NP is exactly equivalent to being able to solve problems in coNP (just apply “not”). Of course, if you had an oracle that solves the search problem of SAT it would also solve the decision problem: a circuit is satisfiable iff the search algorithm returns a satisfying assignment. So I don’t know any meaningful sense in which coNP is harder than NP. Note that in complexity theory an algorithm is said to solve a problem in coNP iff it returns the right answer. It is not required to produce any sort of proof that no NP-witness exists. Of course if the algorithm provably returns the right answer then it can be trivially used to produce such proofs. On the other hand, if the algorithm can only be proved to work well in some average-case sense then it doesn’t yield a proof for any individual case.

A SAT oracle would allow you to solve any optimization problem for polynomial time computable cost functions and, as you said, approximate any counting problem when the instances are polynomial time verifiable. To the best of our knowledge, it would not allow you to solve any problem in the higher levels of the polynomial hierarchy (even though P=NP would imply P=PH, because this requires an actual polynomial time algorithm, not an oracle). Even more so, it would not allow solving all problems in PSPACE, EXP et cetera. Apparently it wouldn’t even solve BQP (although my understanding of quantum complexity is very superficial).

jadagul:

My CS sources tell me the premise about 3SAT is actually basically accurate. It’s still in NP, and we still think P !=NP, and we still don’t have any algorithms with polynomial-time worst-case running time.

But we have pretty good heuristic 3SAT solvers, which “usually” return the right answer in polynomial time, or return something close to the right answer in polynomial time. Wikipedia says:

Since the SAT problem is NP-complete, only algorithms with exponential worst-case complexity are known for it. In spite of this, efficient and scalable algorithms for SAT were developed over the last decade[when?] and have contributed to dramatic advances in our ability to automatically solve problem instances involving tens of thousands of variables and millions of constraints (i.e. clauses).[1] …

There are two classes of high-performance algorithms for solving instances of SAT in practice: the Conflict-Driven Clause Learning algorithm, which can be viewed as a modern variant of the DPLL algorithm (well known implementations include Chaff[15] and GRASP[16]) and stochastic local search algorithms, such as WalkSAT.

My sources tell me that we’ve actually gotten good enough at solving 3SAT that it’s pretty common to convert other problems to 3SAT so we can use our 3SAT algorithms on them. Which aren’t guaranteed algorithms, but which work pretty well in practice.

(Note: you can still have asymmetric cryptography when NP-complete problems are “usually” solvable quickly; you just have to pick problems that fall into the worst-case scenario buckets).

Cryptography relies on existence of problem in NP that are hard in the average-case (w.r.t to some samplable distribution on instances). Now, there is an average-case theory of NP-completeness, that is, there are NP-complete problems with samplable distributions s.t. if such a problem was solvable in the average-case then any problem in NP would be solvable in the average-case w.r.t. any samplable distribution (in particular breaking cryptography). Moreover this “complete” distribution can be chosen to be almost uniform (see Impagliazzo and Levin). So, there might be some distributions w.r.t. which 3SAT is easy but these are not the interesting distributions.

Regarding “work pretty well in practice,” I understand this to mean “produce results which are not useless” which is very different from “actually find the global optimum.”

jadagul Source: antisquark

diffractor asked:

Many NP problems can be solved in most practical cases, like 3SAT. Just how much of the complexity hierarchy has "eh, good enough" solutions given current SAT algorithms? #P can be approximated. Intuitively I'd expect coNP problems to still be tricky, as it seems harder to show that SAT is unsolvable than to find a solution on typical instances. Any other examples of hard problems that suddenly become doable w SAT solvers, or NP/coNP/whatever problems where SAT solvers don't help much?

First, no, 3SAT cannot be solved in “most practical cases.” That is, I don’t know any practical use for 3SAT except reducing other problems in NP to 3SAT. So I don’t know how to interpret “3SAT can be solved in most practical cases” except as “all problems in NP can be solved in most practical cases.” The latter is definitely false, otherwise all of cryptography wouldn’t work, not to mention enormous advances we would have in automated engineering, mathematical proof search, synthetic biology and whatnot.

NP and coNP are both classes of decision problems, so being able to solve problems in NP is exactly equivalent to being able to solve problems in coNP (just apply “not”). Of course, if you had an oracle that solves the search problem of SAT it would also solve the decision problem: a circuit is satisfiable iff the search algorithm returns a satisfying assignment. So I don’t know any meaningful sense in which coNP is harder than NP. Note that in complexity theory an algorithm is said to solve a problem in coNP iff it returns the right answer. It is not required to produce any sort of proof that no NP-witness exists. Of course if the algorithm provably returns the right answer then it can be trivially used to produce such proofs. On the other hand, if the algorithm can only be proved to work well in some average-case sense then it doesn’t yield a proof for any individual case.

A SAT oracle would allow you to solve any optimization problem for polynomial time computable cost functions and, as you said, approximate any counting problem when the instances are polynomial time verifiable. To the best of our knowledge, it would not allow you to solve any problem in the higher levels of the polynomial hierarchy (even though P=NP would imply P=PH, because this requires an actual polynomial time algorithm, not an oracle). Even more so, it would not allow solving all problems in PSPACE, EXP et cetera. Apparently it wouldn’t even solve BQP (although my understanding of quantum complexity is very superficial).

theoretical computer science complexity theory
wayward-sidekick

better sorting systems

wayward-sidekick:

I am annoyed because the vast majority of my social circle has started meaning the sortinghatchats version of Hogwarts houses when they say Hogwarts houses and I think it is a bad system. That is, now when I say “Slytherin” people think “Cares about their social circle as a primary, improviser as a secondary” and when I say “Gryffindor” people think “Cares about their deeply felt principles as a primary, charges at things as a secondary”, and so on, and this is not the thing I want to discuss when I talk about people’s Houses.

The primary thing is just a bad simplification of meta-ethics. Like, don’t call a person a Gryffindor, just call them an intuitionist, there is already a name for this thing. Ravenclaw primary is basically just moral realism with an intellectual aesthetic. The secondary thing is somewhat more interesting but I think it’s badly defined. What makes a Gryffindor “charging” different from a Slytherin improvising anyway? Their charge is supposed to inspire others? So Gryffs are basically just more-attractive Slyths now? What makes a Ravenclaw working hard to build tools and use them to solve problems any different from a Hufflepuff working hard to solve a problem? It seems like Ravenclaws are just Hufflepuffs who wait longer to pick a problem to solve.

I get that Hogwarts houses stick together a bunch of traits that shouldn’t actually necessarily be stuck together. Hufflepuffs are stubborn and hardworking and loyal and fair and patient and kind, Gryffindors are chivalrous and honourable and courageous and spirited and rule-breakers, Slytherins are cunning and ambitious and ruthless and look after their own, Ravenclaws are intelligent and curious and knowledgeable and witty. So what if I’m stubborn but selfish, rule-breaking but pretty cowardly, prideful but not too ambitious, witty but with no particular love for knowledge? Where do I fit? When a friend calls themself a Hufflepuff, do they mean they’re stubborn or that they’re kind?

So you have to separate it up somehow. You have a ‘primary’ section that details whether you’re more kind or brave or ambitious or curious, and a ‘secondary’ section that details whether you’re more stubborn or inspiring or sneaky or smart. But I think this can be done way better and I would like everyone to do it better.

Here is the version I use in my head.

A House is an ideal.

Imagine a great hero arrives one day and saves the wizarding world from a great evil. This hero experiences trauma and tragedy, perhaps losing their family or being injured in the war, but they are unbowed and unbroken. The bad guys are throwing everything they can at them to intimidate them and break them, but this hero can look them straight in the eye and charge forwards anyway, because they’re driven by a sense of purpose and a feeling they’re fighting for more than just their own survival. They acquire secrets from the past and great magics by questing far and wide and overcoming every challenge sent their way with a dauntless fighting spirit and endless enthusiasm and some help from their friends. They’re relentlessly aggressive in battle, and they always duel with a little gleam in their eye that says they’re right where they belong. The enemy try to turn them to the dark side but their bright, shining inner principles won’t let them betray their cause. In the end, no matter how powerful their enemies are or how far their reach extends, the enemy breaks before our hero does. And they have a limitless store of energy that lets them play and feast and write songs and play pranks whenever they’re resting between battles. When they win, they return to a position of service to the people rather than grasping at leadership; they were doing this for principles, not for power. That’s the Ideal of Valour, the thing Gryffindors would rest happy if they felt they had lived up to.

Imagine some other threat arises, something that hero can’t batter down with their heroic bravery. Perhaps the hero topples the bad guy and the power vacuum needs filling and there’s a bunch of competing factions dancing on the line between tense truce and outright hostility. And then in the centre of the chaos emerges another hero. They belong to no particular faction, but their absolute loyalty to the welfare of the people has been tested time and time again and been proved absolutely unshakeable. Make peace, they plead. And it’s a long, slow process, but eventually it just… happens. The hero has many friends - they’ve shown themselves a reliable ally to many people in the past - and besides which nobody could seriously plot to assassinate someone so relentlessly cheerful and friendly. They see the best in everyone and work to nurture it, lend a helping hand to every young wizard who might have a bright idea that would build new systems and a new stronger peace, and somehow still make time for their friends. Occasionally there’s a crisis and the hero is, without exception, to be found in the centre of it, working through the night for as many nights as it takes. They make promises, promises that a certain individual won’t be harmed or a certain task will get done, and people lean on them because they’ve never been known to break their word. They are fair and just and kind, both as a negotiator and as a leader, and they eventually bring everyone together into a whole that incorporates the best ideas from all the factions. There’s some rogues, some battling, and the hero responds with endless patience, always on the front lines when they’re needed there and on the back lines performing healing when that becomes a priority, not necessarily winning every battle but stubbornly winning the war. That’s the Ideal of Reliability, the thing a Hufflepuff would be lucky to live up to.

And then maybe some day the wizarding world is in danger again, maybe this time from an ancient monster straight out of myth and song, brought out of hiding to strike by some ancient curse, and nobody can quite figure out what it is or how to harm it or what it wants or where it’s coming from. It doesn’t take three deaths before our new hero walks out of the depths of the library sometime in the small hours, triumphantly clutching a book. It’s in Latin, but that’s okay, learning Latin was part of the fun and the hero is kind of wondering if they’ll have time to pick up Ancient Greek as well when this blows over. They come up with a plan to take the monster down, and it works, because they thought of everything that could possibly go wrong. Of course they did; this is fun to them, this kind of challenge is what they do five of to relax in the evenings, they’ve played out this situation fifty times before in geeky roleplaying games. They never quite lead the charges against the threat, but they’re always there in the background, figuring out the passcodes to get through the ancient doors by cobbling together information from books they read for curiosity’s sake long ago and wild deductions they make on the fly, sparring with their friends with sarcasm and wit in battles of skill to match the duels themselves, escaping every inescapable-seeming situation with a trick they figured out while experimenting to see how magic works. And the achievement doesn’t stop when the threat is put down, because how could it? They love knowledge, they’re doing this for love, not any other motivation. In the hero’s life they come up with a cure for a deadly wizarding plague, reform parts of the ministry to be more efficient using spells of their own refinement, learn to listen to the winds and read the skies and snatch people’s secrets from a mere glimpse of their eyes, and do all of it with a sense of vague aggravation that they’re being dragged away from reading their books. Sometimes there are challengers, sometimes even challengers they actually have to fight rather than just deflecting with clever words, and the challengers very quickly realise that no amount of duelling skill is a match for the knowledge of thousands of years passed down through written words and contained within one ferociously precise mind. That’s the Ideal of Genius, which Ravenclaws dream of living up to.

And then there’s the individual who survives all of these threats, never quite standing up and declaring themself to be the hero, never coming forwards so boldly, but quietly growing stronger all the time. They run when threatened, retreat wherever their position is compromised, strike only when sure of victory. Very few people end up actually crossing them, because most people have been subtly manoeuvred to be acting for their benefit, but those who do don’t live to talk about it. They may not have the duelling skills of a hero, but they’re tricksy, they think things through. Everyone calls them a coward when they run off in the midst of a fight, but everyone owes them their lives when they reappear from a side tunnel to surprise-attack the enemy from behind at the perfect moment. They acquire power and secrets by pretending to ally with the evil power, all the while influencing the threat to be more precise, think more strategically, inflict less collateral damage. They rise to the top of the new government by flitting between whichever factions seem currently most powerful. They carefully shape the other heroes with a succession of well-chosen mentors and gifted books, sometimes openly, sometimes anonymously. And when some threat finally comes along that does threaten them, they are ready for it, they have power and networks and tricks and traps aplenty. They worry about the threat at first, but then it stumbles afoul of four of the twenty traps they set for it and they shrug and go back to secretly ruling the wizarding world. That’s the Ideal of Plotting, which any good Slytherin plans to live up to or at least help their protegees to get closer to.

Of course, no person really lives up to their ideal. I might want to be a glorious hero who fearlessly charges down dragons in the service of her cause, but in reality my willpower is shaky and my guiding principles aren’t quite clear enough. This is where the splitting up happens.

Your desire is what you wish you could be. When you dream dreams of glory and greatness and heroics, what kind of dreams do you dream? Do you see yourself leading the charge against the darkness, building communities and defending and healing, coming up with plans and discovering ancient secrets, or plotting in the background while surviving and gaining power? What is it that you long for? What do you wish you were good enough to become?

Your pride is the quality in yourself you take pride in. A Gryffindor takes pride in the moments in their life when they bravely stood up for others, when they won battles with others or with their fears. A Ravenclaw takes pride in what they know and have discovered, the clarity or speed of their thoughts and the potential of their mind. A Hufflepuff takes pride in their reputation for reliability, the friendships they’ve built, and the things they achieved by force of sheer hard work. A Slytherin takes pride in all the moments they might have lost and yet didn’t, their ability to survive and escape, all the tricks they’ve successfully pulled off and all the plans that came to fruition.

It doesn’t actually have to be what you’re good at. Someone who is poor and doesn’t have much can take pride in the few nice things they’ve managed to acquire. You can be a stupid Ravenclaw who takes pride in the few things they have managed to figure out. You can be a cowardly Gryffindor who treasures the one memory they have of themselves successfully overcoming a fear.

Desires and prides just captures the basic distinction between someone who isn’t brave but longs to be, and someone who takes deep pride in their bravery and wants to do more of it. You might long to be smart enough to live up to a Ravenclaw ideal, but accept that you never will be and take pride in your Hufflepuff determination. You might dream of bravely leading charges like a Gryffindor, but in practice take more pride in the times you’ve narrowly avoided losing with a clever trick than the times you’ve bravely won.

There’s also comforts; the thing you feel comfortable and natural doing. Again this doesn’t have to be what you’re good at, but it usually will be. It’s the Ideal you feel at home mimicking, that comes as easily to you as breathing. Perhaps you wish you were a community-builder and take deep pride in the times you’ve displayed integrity, but in practice you’re comfortable with curling up in the library with a book so that’s what you fall back on; you have Hufflepuffs desires and prides but Ravenclaw comforts. Perhaps you wish you were a long-term planner with tricksy plots and you take pride in the times a plan has successfully worked, but you’re much more comfortable solving your problems by hitting them with hammers; you have Slytherin desires and prides but Gryffindor comforts.

There will also be some variation within houses; a Gryffindor trying to live up to the Ideal of Valour will look a little different to a Gryffindor trying to live up to the Ideal of Chivalry or of Fearlessness. A Ravenclaw aiming for the Ideal of Wisdom will be a quite different person to one aiming for the Ideal of Wit.

Some Ideals are somewhere on the border. Is Patience an Ideal of the Hufflepuffs or the Slytherins? Is Cunning Slytherin or Ravenclaw? Is Honesty a Hufflepuff Ideal or Ravenclaw? How do we distinguish between the Honour of a Gryffindor and the Integrity of a Hufflepuff? These are the people I would call Slytherpuffs or Slytherclaws or Ravenpuffs or Gryffinpuffs and it is up to them to choose with which other people they wish to study and grow, where they feel at home and which other Ideals feel closest to theirs.

Choice is paramount. It doesn’t matter if your desires, prides and comforts are all Slytherin; if you choose to follow a Gryffindor ideal, for whatever reason, you are a Gryffindor. If your desires are Slytherin, your prides are Ravenclaw and your comforts are Hufflepuff, it’s your own choice which is more important to you.

But yeah, desires/prides/comforts seems to work well, to me. I, for instance, have very much Hufflepuff desires, Slytherclaw prides, and Gryffindor comforts. I choose Hufflepuff. I want to tell people that I live up to an Ideal of Reliability, rather than an Ideal of Valour. I follow the footsteps of Helga. But I’ve called myself all the Houses in the past because I wasn’t separating clearly whether I was talking about what I am usually, what I consider to be my best moments, and what I long to be.

And we see this kind of thing play out in the Potter books! Hermione has Ravenclaw prides and Ravenclaw comforts, but she chooses to follow her Gryffindor desires. Neville may not be very good at the Gryffindor virtues, and probably has Hufflepuff comforts, but he has Gryffindor prides.

Frankly, though, you could sort yourselves based on Gryffindor=red, Ravenclaw=blue, Hufflepuff=yellow and Slytherin=green. You could do Gryffindor=fighter, Hufflepuff=cleric, Slytherin=rogue, Ravenclaw=wizard. Just please discuss meta-ethics without passing it through a Harry Potter filter. Meta-ethics is interesting on its own!

I liked this a lot aesthetically. The key question here is what problem we are trying to solve. To me it seems that what we’re getting at here is creating a typology of heroes according to the skills they bring to bear. Here, “hero” is a person who creates (or tries to create) large impact on the world, positive according to some reference system of ethics (otherwise they would be a “villain”).

Now, it seems to me that if we forget about Harry Potter and try to solve this problem for the real world, we will arrive at slightly different categories. I propose the following types:

* Poet: A hero who educates the multitudes and inspires them to great deeds. This includes great artists, writers and political thinkers.

* Courtier (Senator?): A hero who is good at navigating politics and getting people to do what they want (a.k.a. manipulating). This includes great politicians and businessmen.

* Vizier (General?): A hero who is good at administration and optimization of complex organizations. This includes great high ranking public servants and managers. Usually these people are not as recognized by history as the others.

* Scholar: A hero who is good as solving complex problems that require a combination of knowledge, creativity and abstract thought. This includes great mathematicians, scientists and engineers.

Of course, often a hero needs some combination of several of these skillsets. Also, the desires/prides/comforts division is as applicable here as in Hogwarts Houses.

I guess we can roughly round them as Poet = Gryffindor, Courtier = Slytherin, Vizier = Hufflepuff, Scholar = Ravenclaw, but these are not exactly the same.

wayward-sidekick heroism
girldog

novicoyotl:

nanopup:

somilikes:

gaylor-moon:

nanopup:

less futa furries more trans girl furries
the distinction is important

Less futa art in general would be great, more cute non sexualized trans girl art would be lovely

[ requests more futa art and more cute and nonsexualized trans girl art ]

[ requests more art depicting morphological freedom in general ]

shut the fuck up

morhpological freedom??? why do y’all have to try so hard to justify this gross shit? how hard is it to accept that futa  is just some fantasy thing made up by people who like dicks on girls but are still grossed out by trans women? like this doesn’t exist in a vacuum.

@nanopup: Wash your mouth and learn how not to be a bully.

@novicoyotl: How hard is it to accept that other people are allowed to have whatever sexual fantasies they like? That the sexual fantasies people have say absolutely nothing about their non-sexual attitudes? How hard was it to check a few basic facts about the person you’re accusing of being “grossed out by trans women” to discover that they are a trans woman?

The fact that you are anonymous here on tumblr is not a license to forgo your conscience. Try some kindness and human decency, it will be better for you too.

girldog Source: nanopup internet bullying sexual policing

diffractor asked:

(And again, you don't have to answer all of these) Are there examples of poly-time algorithms where the space complexity prevented it from being practically used? I generally hear about long running time being more of an impediment to solving problems than high memory usage, and it seems that most algorithms have a time-complexity that grows way faster than their space-complexity. Is there something that shows that most P problems and NP approximation algorithms need a lot less space than time?

Well, an algorithm that requires t(n) time uses at most poly(t(n)) space (since it takes that much time to use that space), whereas an algorithm that requires s(n) space can use up to 2^{s(n)} time (since this is the maximal number of states it can have), so an algorithm can require much less space than time but not vice versa. On the other hand it is conjectured that e.g. L \ne P i.e. there are decision problems in P which cannot be solved in logarithmic space (in particular if this is true then it is true of problems that are P-complete wrt logarithmic space reductions).

In my career in algorithm engineering it was common enough for memory usage to be an impediment (e.g. when solving huge non-linear optimization problems) - if not fatal then at least requiring consideration - so I can’t say that practice is very different from theory here.

ask computational complexity theoretical computer science algorithm engineering

diffractor asked:

(2/2) What about other mathematical operations and procedures, where only approximate answers are needed? Does approximation usually produce drastic speedups like this, or are there problems that are about as hard to approximate as to solve?

>  (3/2) I mean, are there natural mathematical operations (by which I mean things like nth roots, matrix multiplication, integrals, and that sort of stuff that shows up a lot, not maximization or things from cryptography), where approximation is about as hard as an exact solution? (I just realized that my last question had a really obvious answer)

(context)

Maximization actually does show up a lot. Regarding the other examples, functions of continuous variables that are sufficiently “well behaved” are usually much faster to approximate than to compute exactly since the approximate answer depends only on a subset of digits of the input. For example, if your function is Lipschitz with constant C then an error of \delta in the input yields an error of at most C \delta in the output. A similar observation is true about Hoelder continuous functions.

ask computational complexity theoretical computer science

diffractor asked:

How does the computational complexity of multiplication drop with significant digits? If you want to get the answer to within 1%, and you have a multiplication algorithm running in time M(n), wouldn't it only be used on a finite set of digits (to get 1% precision), so that would be a constant, and getting the 0's right would be A(log(n)) (where A is the addition algorithm (run on lengths of numbers))? (I am practicing CC, and want to know if I'm analyzing this right.) (1/2)

In general time complexity depends on the computational model (e.g. one tape Turing machine, two tape Turing machine, 2-dimensional tape Turing machine, some cellular automaton, lambda calculus etc.). The only thing guaranteed for any two models is that there are polynomials p,q s.t. if t_1 is the time in model 1 and t_2 is the time in model 2, then t_1 \leq p(t_2) and t_2 \leq q(t_1). This is why e.g. P, the class of problems solvable in polynomial time, doesn’t depend on the computational model. On the other hand, the class of problems solvable in time O(n^3) is not invariant. Also, in many computational models it doesn’t make sense to talk about time complexity less than O(n) since it takes O(n) time just to read the input. If you do want to talk about time less than O(n) you need to carefully specify how your model allows it e.g. by reading only the prefix of the input or having random access to the input.

That said, there is a reasonable model under which your analysis is correct. E.g. if you have random access then you can read an O(1) number of digits in O(1) time and measure the length of the input in poly-logarithmic (in many models just logarithmic) time by binary search (assume reading anything after the end returns a special symbol). The addition itself will take poly-logarithmic (in many models just logarithmic) time since it’s polynomial (in many models linear) time in the length of its input which is of logarithmic size wrt the original input. Also, you have to assume you can produce the output in floating point format, otherwise just writing the output will take linear time.

ask computational complexity theoretical computer science
ilzolende

Anonymous asked:

Immigrants don't escape a war zone. They are a war zone.

ilzolende answered:

  • My grandfather fled Soviet-occupied Hungary, and he brought neither Soviet occupation nor more support for communism to Canada and the US. (He’s more opposed to communism than average, I think.)
  • Although the country my grandmother is from was not actually invaded by the Nazis, they definitely had plans to do that. She and her parents did not bring Nazism to the US.
  • I think we’ve had some people flee the French Revolution to the US, and we didn’t end up with another French Revolution.
  • No clue if the Revolutions of 1848 or the Franco-Prussian war led to many refugees in the US, but those also didn’t create war zones, IIRC?
  • I mean, yes, kontextmaschine has pointed out a few cases where various racial and sectarian rivalries continue in the US, but I doubt they’ve gotten close to being a war zone.

Re revolutions of 1848: yes. In a way, they did affect the “creation of war zones” since many of them fought for the Union during the American Civil War. That was probably a good thing, though.

ilzolende history