P vs. NP

Do you think P = NP? Why or why not?

For those who aren't aware:
P means polynomial time. Essentially, problems that are both easy to check and easy to solve. x + 1 = 5.

NP means nondeterministic polynomial time. Long story short, if you have the solution, these problems are easy to verify. But if you don't, then they aren't. They are easy to check, but not easy to solve. Example: if someone gives you a filled out sudoku, you can check to see if it's valid or not. But it's harder to solve a blank sudoku, because that requires solving and checking it. A tripcode is an example of a supposedly one-way function which is, in theory, harder to crack than it is to make/check. But only if you're doing brute-forcing rather than finding a way to crack the algorithm itself.

So why does this matter? Information security. If P = NP, everything is hackable forever and no encryption will ever be secure due to the laws of mathematics. However, many mathematicians think P ≠ NP. But I wonder if that's just wishful thinking. If P = NP, it won't matter if your FOSS software has no backdoors, because it still won't be possible to secure it even then.

Attached: p vs np.jpg (300x168, 9.38K)

Wrong. Polynomial is simply one complexity class. There are infinite other ones that can be used they are just more expensive.

tripcodes are retarded and insecure, just use PGP

...

...

it's an example of a one-way function
and tripcodes aren't inherently insecure as a concept, because you can technically use whatever hashing algorithm and salt you want for it
unless you think secure hashing algorithms aren't possible because P = NP

For an extremely retarded definition of "easy".
Polynomials can have ridiculously huge exponents and/or constant factors, you know.

You are a fucking idiot, if P=NP then my airgapped server doesn't magically become compromised, nor does the formally verified memory isolation provided by something like seL4 magically break down and allow a malicious program running on top of it to compromise the system.

there's airgapped, and then there's "airgapped"
also schneier's law

Ah yes you proved with math that the memory isolation works when in reality it is totally fucking broken.

P will equal NP if N = 1.

Give me my government grant. I've cracked the code.

It's the other way around, P=NP is "wishful thinking" since it allows solving previously impractical problems.
Depends. If P=NP for some impossibly huge constant it won't make a difference in practice (nor would it enable solving any harder problem in practice, only in theory with an arbitrarily large n).

This. If (current) cryptography is all broken the massive massive massive benefits of being able to solve NP problems in P time far outweigh having to update SSL. All of the sudden many forms of perfect optimization becomes far easier.

I remember some time ago, I was told that from what everything has transpired, it seems that P ≠ NP.

From my take with probably sloppy comparison, I'll take a kind of travelling salesman approach.
Imagine that you want to explore and make a map of the universe, given infinite time you'll eventually visit everything, but that will only work if the universe is in a completely static state since new galaxies are created, and other dies while you are travelling around.
So the only way that you could somehow know what the universe is, is to know the state of everywhere at the same time. Which means that you need to be outside the universe to be able to observe it all at once.
Since you can't go out, then P ≠ NP. That's how I see it.

There is still mathematics that deals with imaginary numbers and other domains, but it's still "bounded" by the universe. The comparison would be having math beyond infinity.

Yeah seems legit.

Have you figured out what N is?

N is one if P is already solved. Otherwise N is the amount of time/effort needed to solve P.

...

Proving that a fast algorithm exists does not mean you magically become aware of that algorithm. Also:

ya don't say anonnn

Agreed. Total consciousness, omniscience, or God.
Disagree. Being outside the universe means you have no way to observe the universe. What is observable outside a thing? Only the energy patterns interacting with it. You don't see an apple, you see the light bounced off an apple. If your light, or whatever medium you are using to measure, feel free to use Hawking radiation if you'd like, is "leaving" the universe to travel "outside" of said universe to you, the observer...all you've done is increase the size of that universe (the light traveling out and you as an observer are now the new boundaries of the universe).
You can't escape The Matrix, Neo.

Attached: tired.jpg (487x750, 131.89K)

Intuitionists on suicide watch.

kek

The proof for P=NP might however give some clues of where to look. Besides, investing ressources into the search for an algorithm wouldn't be a potential waste anymore.

It would be far easier to prove P=NP, if that's true, than it is to prove P ≠ NP, if that's true .

The hypothetical proof of P=NP would be constructive. You have a lock, you find a key that opens the lock.

By contrast, a proof of P ≠ NP would not be constructive . You have to prove that the lock is unbreakable.

The fact that we still can't find a P-algorithm for any NP-complete problem after all this time adds to the case that P probably isn't equal to NP. A proof would still be nice tough.


Actually, proving a fast algorithm exists gives you an method to compute it. This isn't set-theory voodoo where you make use of non-constructive axioms. The method itself may be incredibly complex, but it's a matter of time, not existence. The most basic proof a fast algorithm exists is to build it.

not how that works

Bullshit. Complexity proofs don't require constructive logic and work just fine with set theory.