Real quick question, does p = np?

Nah bro.

Free the P!

>>8210290
If n=1, yes.

>>8210290
50/50

it either does or doesnt

>>8210290
Yes, thought there is no way to verify it.

>>8210290

Yes.

P = Pineapple

N = Nignogs

NP = Nignopple

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

>>8210290
N=1

Does 2=n2

>>8211590
Divide both sides by 2. N0.

File: maxresdefault.jpg (130KB, 1920x1080px) Image search: [Google]

130KB, 1920x1080px

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

>>8211569
so:

Pineapple=Nignopple

all pineapples are actually nignopples?

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

>>8211586
>>8211595
Infinitesimal Keks.

>>8211610
p=0

>>8211638
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 >>8211575 and >>8211615 posted. Passwords could be cracked on the first try, pretty much anything that requires brute-forcing today could be solved easily.

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

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

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

File: Carl-Saganp.png (303KB, 600x411px) Image search: [Google]

303KB, 600x411px

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.

File: 13726734_10209604836908241_7204507471723724310_n.jpg (89KB, 800x494px) Image search: [Google]

89KB, 800x494px

>>8211892

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

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

>>8211605
correct famme

>>8210290

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

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

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

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

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

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

>>8212081
why did you even bother to post

kill yourself

>>8211642
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?

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

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

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

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

File: thuggga WHAT.jpg (80KB, 656x636px) Image search: [Google]

80KB, 656x636px

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

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

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

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

>>8211615
Like, Fermat-Wiles, uh ?

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

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

>>8212804
Sometimes it takes centuries

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

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

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

>>8212756
I get it now. Thank you for the advice.

P=NP is undecidable in ZFC.

>>8211610
>>8210290
>>8210365

P=NP IF

P=0
N=1

Thats all

>>8211615

IF:

P=2
N=1

Does P=NP?
Answer: yes

PS: fuck you

>>8214627
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?

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

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

>>8210365
>>8211586
>>8211590
>>8211641
>>8214627
>>8214629
I think we got the joke guys

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

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

If and only if p is the identity element.

>>8212085
>>8216394
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?

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

>>8211569
Why did I fucking lose to this/

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

>>8211605
They're about to be!

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

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

>>8211547
Most likely not.

>>8211598
I'm with this guy, unfortunately it seems unlikely

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

File: jewish transhumanism.png (1MB, 1354x1606px) Image search: [Google]

1MB, 1354x1606px

>>8216657
>(((singularity)))

P=NP implies the axiom of choice. Huehuehue

>>8217245
Go back to Freital Hans

File: 1464475588869.jpg (128KB, 640x618px) Image search: [Google]

128KB, 640x618px

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

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

>>8217253
Falsehood implies anything, tho.

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

>>8210290
No idiot. P = P

Smh

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

>pol-fags
>>>/out/

>>8211575

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.

>>8211892

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.

>>8221127
>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?

>>8211605
/sci/-Science and Math

File: 241135841178.jpg (160KB, 1024x771px) Image search: [Google]

160KB, 1024x771px

>>8221375

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