Procrastination, NP vs P, and Delicious Links

While Elecia was supposed to be working on her?Creating Chaos and Hard Faults ?for the Embedded Online Conference (coupon:?EMBEDDEDFM), she took the opportunity to answer a question on the Embedded Patreon slack.?

Sila noted that in a recent episode,?474: It's All Chaos and Horror , we talked about P and NP problems but we didn't explain why those are interesting during the show. Here is her explanation.

P means polynomial time to solve this... so the time to implement an algorithm to solve Problem with n elements is n^x where x is some exponent that depends on the problem.

You have 50 elements in a list and you want to sort them (n=50, Problem=quicksort). The?quicksort ?algorithm runs in O(n^2) time, so if you ran it with n=5, you'd expect it to take

time = <fixed time> + <constant multiplier> <5^2>

And if you ran it with n= 10, it would take

time = <fixed time> + <constant multiplier> <10^2>

The cool thing here is that you can predict how long n=50 will take.

With me?

NP means?not?polynomial. There may be a way to say how long an algorithm will take: O(c^n) says that the algorithm will take some constant (c) raised to the number of element. If n=2 then

time = <fixed time> + <constant multiplier> <c^2>And if n = 10, thentime = <fixed time> + <constant multiplier> <c^10>

which is an egregiously large number (compared to polynomial solutions). It doesn't matter what c is (as long as c isn't 1), algorithms with exponential orders increase very, very rapidly so the number of elements means the time it takes to solve probably goes to "takes much too long" very quickly.

The?travelling salesman ?is a common example. It is O(n!) so for every city you add, the time it takes goes up very quickly.The great question in computer science is "what if NP=P?" which is to say, "what if someone could prove that all the non-polynomial algorithms could be run in polynomial time?"

Now, the answer is obvious, you can't do that. Because polynomial and not polynomial are not the same. But weirdly they persist in this delusion because it is a fun puzzle, like proofs are a fun puzzle. I don't get that part.

TL;dr:

• P = solvable in reasonable amount of time
• NP = really hard problems
• Elecia?doesn't like math proofs.

Nordic Semiconductor empowers wireless innovation, by providing hardware, software, tools and services that allow developers to create the IoT products of tomorrow.?Learn more about Nordic Semiconductor at nordicsemi.com , check out the DevAcademy at academy.nordicsemi.com and interact with the Nordic Devzone community at devzone.nordicsemi.com .

Weekly links:

• What to look more into how a processor boots? There is a neat post about the Raspberry Pi Pico boot process . There is a lot more on that site.?
• Voyager 1 spacecraft started sending gibberish in November but is finally talking again (from NASA ). Apparently, their RAM has some damage and they reprogrammed the extra-solar-system spacecraft to avoid the bad RAM. (Is it an over-the-air update if there is no air?)
• Retro-computing continues to create weird scenarios. Now you can work on C64 assembly projects in VS Code. ?Sounds like a good intro to C64 programming in general!

Memfault is making software the most reliable part of the IoT with its device reliability platform that enables teams to be more proactive with remote debugging, monitoring and OTA update capabilities. Try Memfault's?new sandbox demo at?demo.memfault.com .?Embedded.fm ?listeners?receive 25% off their first-year contract with Memfault by booking a demo here:?https://go.memfault.com/demo-request-embedded .

Upcoming Show

Our next episode will come out Wednesday May 1st with Lee Wilkins, talking about theOpen Hardware Summit fromOSHWA (May 4-5, 2024 which is why we're releasing it early).?

Patreon To join the Embedded?conversation?on Slack, support us on?Patreon .

Interested in sponsoring the newsletter or the show? Drop us a line at sponsorship at embedded.fm and let's talk! ??

Sign up to our email newseletter here .