/tech/ - Technology★

>>996175 (OP)

>If P = NP, everything is hackable forever and no encryption will ever be secure due to the laws of mathematics

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

>tripcode is an example...

tripcodes are retarded and insecure, just use PGP

>>996182

>comparing tripcodes to pgp

>inb4 anon comes backing his opinion with a formal proof

>>996182

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

>>996175 (OP)

>Long story short, if you have the solution, these problems are easy to verify.

For an extremely retarded definition of "easy".

Polynomials can have ridiculously huge exponents and/or constant factors, you know.

>>996175 (OP)

>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.

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.

>>996208

there's airgapped, and then there's "airgapped"

also schneier's law

>>996208

> nor does the formally verified memory isolation provided by something like seL4

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.

>many mathematicians think P ≠ NP. But I wonder if that's just wishful thinking.

It's the other way around, P=NP is "wishful thinking" since it allows solving previously impractical problems.

>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.

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).

>>996469

>It's the other way around, P=NP is "wishful thinking" since it allows solving previously impractical problems.

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.

>>996532

>be me

>be outside computer

>know state of computer

Yeah seems legit.

>>996456

Have you figured out what N is?

>>996554

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

>>996182

>not gpg

>>996492

>All of the sudden many forms of perfect optimization becomes far easier.

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

>>997961

>does not mean you magically become aware of that algorithm

ya don't say anonnn

>>997961

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

Intuitionists on suicide watch.

>>998724

kek

>>997961

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.

>>1000008

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.

>>997961

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.

>>1000559

>constructive logic can't prove something is wrong

not how that works

>>1000559

>This isn't set-theory

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