Quickie: P vs. NP

There are some problems which, by all appearances, are much easier to check than to solve. We rely on this every day--even though it's never actually been proven!

_____

[dale]

"We'll get to [time travel] in a future quickie." I see what you did there.

[evensgrey]

How the truth value of P = NP connects to the topology of the universe is going to be interesting.

[artemiasalina]

I've already proven that time travel is not possible. The way I did it was to first observe that the internet is being archived and these archives will be available to people of the future forever. Then I posted a long insulting open letter to people of the future, calling them girly men who prance around in primary-colored spandex tights eating blue food and challenging them to punch me in the nose if they think they're tough. Since no one wearing primary-colored spandex tights has punched me in the nose I surmise that time travel is impossible.

[TECHN]

P vs NP is one of those things where it is "easy" to prove that P = NP (by proof by contradiction, solving an NP-complete problem in Polynomial time) but the other way around is hard because we don't even have a clue as to where to start. (by easy and hard, I mean relative to the other)

[JasonParthum]

If time travel were possible, wouldn't it have happened by "now"?

[pierrecolin]

Actually, P vs. NP is only about problems for which if someone proposes a solution, you can check if it’s correct in polynomial time. It’s not about all problems. Take the travelling salesman problem. “Is there a hamiltonian cycle of length less than n?” is an NP problem since given a cycle you just have to measure its length to answer, but “Does the shortest hamiltonian cycle have length n?” is not (or if it is, it’s unproven) because even if you’re given a cycle, to answer you need to check if it’s indeed the shortest. Similarly, the economic calculation problem is probably not NP.

[manuelsevilla]

Shane, I love when you rant about cryptography, or math in general

[RockawayCCW]

Even if time travel is possible it isn't survivable because Earth is whizzing thru space at 86, 000 miles per hour. Go back in time even a few minutes, and you'll be floating dead out in space and Earth will be thousands of miles away.

[SuperAtheist]

Technically speaking we're always time traveling.
I think the only way to stop time traveling is to space travel at the speed of light.

[RockawayCCW]

The only math I care about is whether I have enough money.

[ctrlaltdebug]

Don't you hate it when people say "exponentially" when they mean "polynomially "?

[AxelXGabriel]

Hey Shane, just a quick question, what happened to that Lord Killian video that made fun of the Flat Earth/ODD channel? It was legit very good and I couldn't find it.

[deadalnix]

Well, not quite. If you find a solution in then it might as well be an NP problem, so in practice, it's not that big of a deal for crypto systems.

In fact, consider that factorization is something that can be done in quasi polynomial time (the exp factor is vanishingly small and doesn't matter for any practical value). And yet, RSA is still widely used, even though keys are typically in the 4096bits rather than 256bits because of this.

[nrdmn]

Just a million bucks for solving the question to life, the universe and everything? Seems kind of paltry to me. My answer, I think, woul be "42".

[banderfargoyl]

That NP contains P is obvious from the spelling. Where's my million?