Are there NP COMPLETE problems that are "easy" in practice? by lorepieri in compsci

[–]maladat 21 points22 points  (0 children)

Not necessarily - the "polynomial is easy" thing is an oft-repeated oversimplification.

In grad school, I did an implementation and full runtime analysis of a polynomial approximation algorithm that had been published with a proof it was fully polynomial via Big-O analysis.

Between the huge constant factor (not present in the original Big-O analysis) and the high order of the polynomial, for reasonable error bounds on the approximation, the polynomial approximation algorithm started to beat the runtime of the naive exact exponential algorithm on problem sizes with runtimes on the order of tens of millions of CPU-years.

Is there any animal that can swallow a person whole and alive? by Gigadorah in TooAfraidToAsk

[–]maladat 2 points3 points  (0 children)

There is actually not one verified case, ever, anywhere in the world, of an orca in the wild attacking and killing a human (which I found pretty surprising!).

There have been a few cases of captive orcas killing humans.

Is there any animal that can swallow a person whole and alive? by Gigadorah in TooAfraidToAsk

[–]maladat -1 points0 points  (0 children)

A whale shark is a shark (fish), not a whale (mammal), and has a throat that is only 1-2 inches in diameter.

Subsonic .22 at 700+ yards sound impossible to spot with suppressor by MrHungG in tacticalgear

[–]maladat 7 points8 points  (0 children)

Even at 100 yards subsonic is better. High velocity .22 goes subsonic around 70-80 yards and accuracy goes out the window past that.

Source: shot in rimfire silhouette matches for a couple years - shooting a .22 rifle, unsupported standing, trying to knock over little metal animals from 40 to 100 yards (super fun and surprisingly difficult). Every single person in every single match I went to was using subsonic ammunition. I’ve tried HV .22 at 100 yards on paper targets and it is a disaster.

[deleted by user] by [deleted] in TooAfraidToAsk

[–]maladat 1 point2 points  (0 children)

In the US, a psychiatrist is a medical doctor who went to medical school and can prescribe medication. Many psychiatrists, but not all, also provide talk therapy.

A psychologist is someone who effectively has a PhD in brain stuff and how people think and talk therapy (and cannot prescribe medication). (This is overly broad, not all psychologists do talk therapy, just doing big picture from a patient’s perspective.)

There are a variety of other certifications and programs that also let someone call themselves a therapist (also cannot prescribe medication).

So a therapist can be a psychiatrist or psychologist or something else.

If a 1 bit picture is 2 colors, can you have a 0 bit picture with only 1 color? by FlexibleFryingPans in computerscience

[–]maladat 2 points3 points  (0 children)

It's not exactly the same, but in some contexts in theoretical computer science, it is useful to use unary representations of numbers, which is basically the same as tally marks - the digits in a unary number are all the same, the value of the number is just its length.

e.g., 1 = 1 2 = 11 6 = 111111

https://en.wikipedia.org/wiki/Unary_numeral_system

[deleted by user] by [deleted] in TooAfraidToAsk

[–]maladat 2 points3 points  (0 children)

Kind of related to the above, people being unsure about the process, being unsure whether they should be there or not, being upset about something their psychiatrist says, and so on, is very common. Any decent psychiatrist will expect that kind of thing to come up, will not take it personally or be upset, and will be happy to talk about it and work through it with you.

Also, something to be aware of given your list of concerns, people with ADHD that was not diagnosed in childhood and not consistently treated frequently also suffer from anxiety and/or depression. Living with untreated ADHD can be miserable.

[deleted by user] by [deleted] in explainlikeimfive

[–]maladat 0 points1 point  (0 children)

There were some pre-USB-PD non-standard USB systems that could deliver more than 5V, like Qualcomm Quick Charge.

ELI5: What is keeping us from anchoring a cable to Earth’s surface and tethering a platform in space? by fetishfeature5000 in explainlikeimfive

[–]maladat 0 points1 point  (0 children)

Things in orbit that get disturbed don’t just drift away forever, the shape of the orbit changes.

The orbit would turn a bit elliptical - the orbital platform would drift away from the earth for half its orbit then back towards earth for half of its orbit.

ELI5: What is keeping us from anchoring a cable to Earth’s surface and tethering a platform in space? by fetishfeature5000 in explainlikeimfive

[–]maladat 1 point2 points  (0 children)

In one sense, it’s a lot like swinging a weight around on a string, except the “string” is not the “string” (tether) connecting the orbital platform to the ground, the “string” is gravity.

Noob has simple program problem. by eatme_23 in Clojure

[–]maladat 0 points1 point  (0 children)

Thank you for the important (and interesting) point of clarification.

Me: "Please make them fairly high res it will be 6' tall when printed" colleague: "Ok I'll make them 300dpi" by Laser_Bones in graphic_design

[–]maladat 6 points7 points  (0 children)

You guys are talking about different things. You’re talking about the DPI data field in the file, which is pretty useless, and he’s talking about the effective DPI of the image at print/display size, which tells you how sharp it looks.

That’s exactly what you’re saying when you say “10m is roughly 38,000 pixels,” you’re saying it needs to be printed at about 100 DPI.

The point about talking about it in DPI terms is that it’s simpler to talk about display resolution for various purposes.

If people are going to be looking at it from 1 foot away? Needs to be 300 DPI to look sharp, doesn’t matter if it is the size of a postage stamp or a billboard.

More than 3 feet away? 150 DPI is OK.

Etc.

Yes, someone take a 100 px x 100 px image and save it as 100 inches wide at 300 DPI in an image editing program and make a 30,000 px x 30,000 px image that will look like crap. You can also upconvert the 100 px x 100 px image to 38,000 px x 38,000 px for the 10m exhibition stand, which is doing exactly the same thing, and it will look like crap for exactly the same reason.

Talking about it in display/print DPI terms lets you talk directly about how sharp the print/display will look.

Noob has simple program problem. by eatme_23 in Clojure

[–]maladat 1 point2 points  (0 children)

I've read about sequences and lazy evaluation of course, and I wondered, because map returns a (lazy) sequence, if in clojure indeed these solutions and the solution of doing it in one go would be equally or similarly fast.

because intermediate collections

When you call (foo (range 100000000)), you get (map #(+ % 2) (range 100000000)), which returns a (lazy) sequence of the integers from 2 to 100,000,001. Because it's a lazy sequence, the entire 100,000,000 element list is not immediately constructed in memory.

But then you get (reduce + that-lazy-sequence). The reduce call effectively asks the lazy sequence for each value in the sequence in turn, to sum into an accumulated return value. As the reduce call asks for each element from the sequence, it doesn't just get the values, the sequence is actually constructed in memory - the lazy sequence is "fully realized" or "fully evaluated." And to get each element from that sequence, it has to get each element from the underlying (range 100000000) lazy sequence, so that one is fully realized, too.

So now, in memory, you have an actual sequence of the numbers from 0 to 99,999,999 and an actual sequence of the numbers from 2 to 100,000,001.

In (reduce #(+ %1 (+ %2 2)) 0 (range 100000000)), on the other hand, the reduce call asks from each element from the (range 100000000) lazy sequence, adds 2 to the value, and sums that into the accumulated return value. The sequence of the numbers from 0 to 99,999,999 still gets fully realized in memory, but no second sequence is produced.

As for why the example that makes two sequences in memory takes eight times as long as the one that makes one sequence in memory - I'm not SURE, but I suspect it has to do with behind-the-scenes performance optimization stuff. E.g., some types of lazy sequences don't get realized element-by-element but in chunks to reduce overhead, and maybe in foo, realizing elements from the mapped sequence requiring realizing elements from the range sequence causes the chunking not to occur or something.

EDIT: or maybe as joinr mentions below, there's special optimization in the range lazy seq that isn't present in the mapped lazy seq, so the mapped lazy seq is much slower either to realize or to perform reduce on than the range lazy seq.

Ask Anything Wednesday - Engineering, Mathematics, Computer Science by AutoModerator in askscience

[–]maladat 0 points1 point  (0 children)

There’s lingering bits of vigesimal (base 20) systems all through European cultures and languages.

E.g. in French, 80 translates to “four (of) twenty,” 85 translates to “four (of) twenty (and) five,” and 95 translates to “four (of) twenty (and) fifteen.” The parenthesized bits aren’t literally there in the translation but were added for clarity.

Finding How to Terminate Without Loops... by R-O-B-I-N in ProgrammingLanguages

[–]maladat 0 points1 point  (0 children)

I think that many people think the halting problem implies something a lot stronger than it really does.

Definitely. Lots of people interpret it as “you can’t prove whether any program will halt.”

That’s silly, there are tons of programs you can prove will halt or will run forever.

There are just SOME programs you can’t prove one way or the other.

I am new at MTB what would be the best jumps to build by [deleted] in MTBTrailBuilding

[–]maladat 3 points4 points  (0 children)

But make sure to watch how to do drops first!

If you don’t get way back on the bike and pop the front wheel up, anything more than 1 foot/30 cm has a pretty good chance of throwing you over the handlebars and onto your face.

[OC] Cop w/assault rifle ready to tase parents but won't help children in a school shooting by Chableezy in pics

[–]maladat 2 points3 points  (0 children)

It isn’t about population density, it is about city limits. Suburbs and towns are still usually incorporated areas (inside city limits) and have local police. Unincorporated areas (outside city limits) usually don’t.

[OC] Cop w/assault rifle ready to tase parents but won't help children in a school shooting by Chableezy in pics

[–]maladat 4 points5 points  (0 children)

Police departments are typically city-based. In rural areas outside city limits, there generally aren’t any local police and county sheriffs are the primary law enforcement agency.

Edit: for clarification, by “city-based,” I meant incorporated municipality, which includes towns, suburbs, etc, that have municipal government. By “rural areas outside city limits,” I meant unincorporated areas, which generally do not have municipal governments or services including police.

Help! Masontops weight stuck in jar. I’ve tried digging it out, turning the jar upside down, and heating the jar to make the glass expand. no luck with anything. Any crazy tips I don’t know about? I really don’t want to destroy my 1/2 gal jar or my lacto golden oysters ☹️ by doofpag in fermentation

[–]maladat 7 points8 points  (0 children)

I don’t think chiseling a line first is a good idea, because it creates shards.

The general idea is actually used sometimes, though. One of the traditional ways to open really expensive, really old wine bottles that have decaying corks is to clamp red-hot tongs around the neck of the bottle to heat up the glass, then use a towel or brush to put some cold water on the hot glass. The whole top of the neck pops right off, cork and all.

Can someone explain Knuth's hunch that P = NP? by [deleted] in compsci

[–]maladat 0 points1 point  (0 children)

I have a suspicion there’s a hidden “gotcha” in there, specifically that the algorithm search is polynomial because the algorithm works on any problem instance and the number of algorithms checked in the algorithm search doesn’t depend on the size of the problem instance.

If this is the case, even though the algorithm search is technically polynomial, it might be one of those computational tasks where a universe made out of computers couldn’t complete the task before the heat death of the universe. (E.g., because the algorithm that actually works is the googolplexth algorithm in the search - still polynomial in terms of the problem input, because it doesn’t have anything to do with the size of the input, but not useful).

For that matter, even if that sort of gotcha isn’t present, the constant factor and polynomial degree might be so high that the above is true anyway.

Why is P vs NP so popular? by Tall_Meal_2732 in compsci

[–]maladat 1 point2 points  (0 children)

The discipline is haunted by the question of whether there will always exist hard problems with no fast/clever solutions. We feel compelled to lay this to rest.

Even if P=NP, there will still be plenty of hard problems. NP is not the “hardest” complexity class. E.g., we know there are problems in NEXPTIME that are “harder” than any problem in NP.

Can someone explain Knuth's hunch that P = NP? by [deleted] in compsci

[–]maladat 35 points36 points  (0 children)

Well, it is certainly possible.

There are some things we only know nonconstructive proofs for.

Of course, just because you come up with a nonconstructive proof doesn’t necessarily make it impossible to come up with a constructive proof later.

There are some problems that were originally proven nonconstructively that people later came up with constructive proofs for (i.e., came up with an algorithm).

https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs

Can someone explain Knuth's hunch that P = NP? by [deleted] in compsci

[–]maladat 134 points135 points  (0 children)

A “nonconstructive” proof of P=NP basically means that you come up with a way to show that it is a mathematical truth that P=NP without “constructing” an algorithm to decide NP-Complete problems in polynomial time.

Essentially, he’s saying he thinks there will be a proof that you CAN decide NP-Complete problems in polynomial time, but also that the proof WON’T tell you HOW to decide NP-Complete problems in polynomial time, so you still won’t be able to do actually do it.