Real quick question, does p = np?

Real quick question, does p = np?

Nah bro.

Free the P!

If n=1, yes.

Maybe

50/50

it either does or doesnt

Yes, thought there is no way to verify it.

Yes.

P = Pineapple

N = Nignogs

NP = Nignopple

No. If it were true then the world as we know it would end.

N=1

Does 2=n2

Divide both sides by 2. N0.

>p = np?
First serious answer in thread:
Seems unlikely.

so:

Pineapple=Nignopple

all pineapples are actually nignopples?

any other possibilities?

not probable. we'd have proven it at this point if it was true. it would bork pretty much all crypto

Can someone explain this problem as if to an idiot? I don't understand what Wikipedia is trying to explain about it.

I've a proof but I can't compute the answer.

Infinitesimal Keks.

p=0

From my limited understanding:

P: solving an answer
NP: verifying an answer

If they are equal, that means you can solve pretty much anything quickly, which is why and posted. Passwords could be cracked on the first try, pretty much anything that requires brute-forcing today could be solved easily.

> solve pretty much anything quickly
P=NP would change nothing, only tell us that if we can verify a problem in NP time we can solve it in P(olynomial) which can be N^1, N^2, N^3, or N^10000. Most of the cases it would be a very high order of N.

[math]N^\text{fuckton}[/math] still beats [math]2^N[/math] for [math]\frac{N}{\log N} \geq \frac{\text{fuckton}}{\log 2}[/math].

good luck running [math] N^fuckton [/math] in a fucking trillion trillion trillion years m8 :^)

I regularly think about this question, not because I necessarily think I can solve it, but because it's a challenging problem that I think is worth being thought about.

It seems right now, however, that any academic work on the subject is just quickly becoming unproductive. One person makes an assumption to say that it's hard to approximate one problem; somebody else makes another assumption using that assumption to say something else is hard to approximate. Everything thought on the topic right now rests on assumptions. Some of the work is brilliant, but nobody is really doing anything to prove any of those assumptions.

I largely think that the problem is that people don't think about the problem from an unbiased perspective: people want to form an opinion and stick to it, and a problem like this shouldn't really be political.

Let's take a completely unbiased view of the problem right now: can a deterministic Turing machine produce a solution in polynomial time for any decision problem for which a non-deterministic Turing machine can do so? Alternatively, you can reduce the problem to an equivalent question: given an answer to a problem whose answer can be verified in polynomial time, is there always a deterministic algorithm that can find a solution in polynomial time?

As a result of the Church-Turing thesis, we can say that, if there exists a polynomial-time solution to a NP-complete problem, there exists a polynomial-time solution to all NP problems. Alternatively, if you can prove a lower bound on the complexity of a solution to any one NP-complete problem, the existence of a polynomial-time solution to another NP-complete problem becomes a contradiction.

My own feeble research into this problem has been motivated by this realization. My intuition is this: choose a class of problems in which NP-complete problems exist--for example, combinatoric optimization problems in graphs. Next, develop a framework for algorithm development in this class which is guaranteed to produce correct algorithms while admitting progressively tighter lower bounds based off of well-known characteristics (not assumptions) of this class of problems. The key value in such an approach is that it assumes no answer; however, it provides a direct path of effort which can clearly and definitively lead to a conclusion in one form or another (P = NP if a polynomial-time algorithm is produced; P =/= NP if a lower bound is obtained which is superpolynomial in terms of complexity with respect to n) without having to cling to a conclusion before I even begin any real kind of analysis. To be honest I have very little experience in coding, in fact my major of study at the moment is Biochemistry and Applied Mathematics with a minor in Neuroscience.

Thats a very easy problem.

P = P
N = (value of P - value of P)
NP therefore, is equal to P.

Therefore, you only have to cancel the values of P to obtain N.

To clarify:

P = {after 1/100 of human second, 0; after 1,50/1 of a human second, 4}

N = {after 1/100 of a human second, 0; after 1/50 of a human second, 1; after 1/25 of a human second, 2; after 1/1 of a human second, 3; after 1,50/1 of a human second, 4} - {value of P} = NP

>P=NP would change nothing, only tell us that if we can verify a problem in NP time we can solve it in P(olynomial) which can be N^1, N^2, N^3, or N^10000. Most of the cases it would be a very high order of N.

If P=NP, public key encryption doesn't work.

correct famme

Chris Langan believes he can prove P does not equal NP and he's the smartest man on earth.

nice fucking meme, learn to read will you?
>Most of the cases it would be a very high order of N

this is a very old, unoriginal idea. it's very bold of you to say something like
>nobody is really doing anything to prove any of those assumptions
when you clearly don't know much about computing

just because p=np doesn't mean we can figure out the polynomial time algorithm

not to mention we'd actually have to FIND the specific P algorithm

A year ago I would have said P != NP, with the recent proof that you can perform graph isomorphism in P SPACE complexity I don't know anymore.

why did you even bother to post

kill yourself

10% of comp scientists still think p= np though

Ok, I think I get it. So let's say for example I want to create a computer algorithm for mapping the orbit of every star in the galaxy but I need to know whether or not my algorithm is accurate. If P = NP then I can both run my algorithm and know it's accurate at the same time.

Yeah, this is fairy land. There is no way to both run a program and know it's accurate at the same time. Why are computer scientists chasing unicorns?

Or am I still not understanding the problem?

I know very little about the question, but I think the consensus is leaning towards P != NP (not that that is a proof or anything).

Dude, come on. P = P, therefore P = NP iff N = 1.

No, this is wrong.

P = the set of problems that can be solved deterministically in polynomial-time (which sort of means they can be solved "fast").

NP = the set of problems that can be solved non-deterministically in polynomial-time. An equivalent characterisation is that they're the problems which, given a possible answer, can have that answer verified as being correct or wrong in polynomial time.

P is a subset of NP. But is it a proper subset?

If P = NP, it means that any problem with an algorithm to quickly verify given answers will also have an algorithm to quickly find answers.

Example: given a logic formula, and an assignment of variables to truth-values, you can easily check if this makes the formula true. So this problem is in NP. If the problem was in P, then given the formula you can tell if there is a set of variables that makes it true, or not.

>Why are computer scientists chasing unicorns?
Most people interested in this problem come more from the mathematics side (i.e. the people working in logic, computability, complexity, etc).

>There is no way to both run a program and know it's accurate at the same time.
Yeah. You're completely talking out of your ass.

>we'd have proven it at this point if it was true

I don't understand the problem. Maybe you're using jargon I just don't know.

All I understand from these posts is that you're trying to get a computer to both solve a problem and verify it's solved properly at the same time.

Which seems to me logically impossible.

If I create a solution to a problem on computer A then use computer B to check the solution I then need computer C to check the accuracy of computer B in checking computer A's solution and computer D to check the accuracy of computer C checking the accuracy of computer B checking the accuracy of computer A's solution.

I need an infinite number of computers. Or if on one computer I create an algorithm to solve problem X which then needs an algorithm Y to verify the accuracy of algorithm X which then needs algorithm Z to verify and so forth.

Am I understanding the problem now? Seems like still chasing unicorns.

> P = NP iff N = 1
what if P=0. brainlet detected

>Am I understanding the problem now? Seems like still chasing unicorns.
No. Go to wikipedia and youtube.

Like, Fermat-Wiles, uh ?

>All I understand from these posts is that you're trying to get a computer to both solve a problem and verify it's solved properly at the same time.
No. Problems in NP can be verified in polynomial time but not necessarily solved in polynomial time. Those that can also be solved in polynomial time (NOT "at the same time", simply a polynomial time algorithm ALSO exists for solving, not just for verification) are in P. if P = NP, ALL problems that can be verified in polynomial time can also be solved in polynomial time. This does not appear to be the case, but no one has proven so.

Any NP-complete problem can be converted to any other one in polynomial time. If we found one algorithm as a solution, then we could solve all of them. Once a problem is solveable in polynomial time, it is common to be able to reduce it to O(n^6) or lower.
IMO we would have found a solution already if P did equal NP. It's probably been the most studied problem of the last few decades.

Sometimes it takes centuries

sometimes it's just one mistake to regret for a century

its basically a cancelling operation where the result is the same as the input


Im not going to let it all too clear here because computers can use this info in the future for malicious intentions.

>go to Youtube
I hadn't thought of that, I will do so sir.

I get it now. Thank you for the advice.

P=NP is undecidable in ZFC.

P=NP IF

P=0
N=1

Thats all

IF:

P=2
N=1

Does P=NP?
Answer: yes

PS: fuck you

P=0 OR P=1

This is probably a dumb question, but why is factoring the product of two large primes hard if the primes are the keys?
Why can't you just multiply the public prime by guesses that get larger or smaller depending on what the resulting product is in comparison to the actual product?

well that's basically brute force. It would work fine for relatively small primes, but these large primes are very very large

It's not brute force because you don't have to check every possibility.
If the product of the key and the number you guess is way too low, you guess a much higher number.
Then if the product is slightly too high, you guess a slightly lower number.
And just keep honing in like that.

I think we got the joke guys

>Why can't you just multiply the public prime by guesses that get larger or smaller depending on what the resulting product is in comparison to the actual product?
There is no public prime. What is public is the *product* of two primes, and the task is to recover those two primes.

If P=NP, then public key encryption still works but can be broken.

If and only if p is the identity element.

I don't understand, why is it such a big deal? It doesn't change anything to know it's theoretically possible as long as nobody breaks it, does it?

This is the correct answer. not sure what the big fucking deal is.

Why did I fucking lose to this/

When we reach the singularity, you'll fucking see.

They're about to be!

I think the real interesting question is if NP is a subset of BQP or not.

I think computer scientists sometimes forget that mathematicians have such a hard-on for non-constructive proofs.

Most likely not.

I'm with this guy, unfortunately it seems unlikely

P = [1 0; 0 0], N = [1 1; 0 1]

>(((singularity)))

P=NP implies the axiom of choice. Huehuehue

Go back to Freital Hans

That epic tfw feel when you're sharing memes with you're /b/ros XDDDDDDDDDDD

forward slash join showderp so dats how der playin xDDDDDDDDD POKEOMN!!!!! SHOWDOWN!!!!!!!!!!!!! RUELS!!!!!!!!!!!!!!!!!!!

Falsehood implies anything, tho.

this picture shows how afraid pol-fags actually are of science

Either true AI or engineered babies with super genes will be enough to 'kill' all humans, including the superior white race.

We simply wouldn't be able to compete.

No idiot. P = P

Smh

>afraid
No newfag, we simply recognize that transhumanism is life-denying eschatology masquerading as science.

>pol-fags

If it were true, the world would be as it always has been. You simply have to learn to live in a world where there is yet another true thing that you don't understand.

I posted this months ago. I'm just curious: why did you copy-pasta this? I didn't really contribute anything more meaningful than what you would be able to find on Wikipedia.

>I posted this months ago.
Is this still your current position? Because it doesn't make much sense. In particular, what makes you think that others haven't also thought deeply and unbiasedly about the problem? And where do you get that idea that researchers don't aim for unconditional results?

Veeky Forums-Science and Math

...

Why can't p=np be figured out by using less complex things we already know the answer and all the solutions?