Can you prove that P=NP?
N = 1 or P = 0
ez, can't believe it took computer scientists so long to figure out.
>>7966014
Its not algebra you mong
>>7966014
kek, nice man. What are you going to do with the prize money?
>>7966073
No can solve the problem (yet), its an unsolved problem
>>7966093
You solved a simple algebra question that uses the same notation, not whether the complexity classes P and NP are the equal
>>7966014
are you retarded? the proof is
P = NP
P - NP = 0
P(N - 1) = 0
Thus either P = 0 or N = 1
>>7966103
I didn't write the proof down because I didn't want someone else to claim the prize money, good job fucking it up for the both of us
>>7966106
dont worry bro I made a mistake in there and I wont say what it was so we good
>>7966097
why are you so autistic?
>>7966136
Im on 4chan arent I?
e^2Pi*i=cos(2Pi)+isin(2Pi)
e^2Pi*i=1
2Pi*i=log(1)
2Pi*i=0
2P(i)^2=0
-2P=0
P=0
P=NP Q.E.D
>>7966014
>>7966103
This joke is still funny.
>>7966281
>Yet noone seems to grasp that this issue is related to complexity theory
They know full well. It's called shit posting you should try it.
It is easy to solve problems like 2+2 but it is hard to solve other problems.
Therefor p =/= np
id say there will be always problems in which changing the algorithm will bring shorter time complexity.
so P will never reach NP, no matter how far in the future this question will be asked.
>>7966005
What is the simplest problem to work with? Small grid sudoku?
>>7966466
apart from to easy things id say a transcendent equation such as x + sin x = 0
Start with a list of all numbers between 1 and 9999. Remove 1 at random.
Which number was removed? P or NP?
>>7966005
what if i prove that the P vs NP problem is in NP-complete? would i win the price?
>>7966503
part of EXP, not part of P id say
>>7966005
do you actually think that some anon will casually come strolling along and solve P=NP one day in a short shitpost?
>>7966295
>mfw trolling has gone from make other people act retarded to let me act retarded
> Asking a question on the board consists of mostly edgy high school kids and expect serious answers.
You're dumb. Go kill yourself.
Mods should just remove this board, it's hitting new low everyday.
>>7966005
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.
>cont.
>>7966643
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.
Next year I'm going into a pretty competitive graduate school where I'll be expected to come up with my own research topics. This is one of the directions I'm considering currently because (1) in the best (and simultaneously least likely and most unreasonable) case, I get to be the wizard who solves what is arguably the most important problem in computer science and because(2) in the more likely situation, I can produce some kind of tool that offers some marginal improvement for algorithm design and analysis in an incredibly niche class of problems.
I'm also considering against this approach because I don't know if I have the courage to actually face my adviser and say, 'Let's solve P vs NP!!11'
I'll probably just take the easy way out and just do research in an area that's at least a little farther away from being ridiculous.
>>7966658
Good luck bro
>>7966663
Please dont for the love of Richard Feynman keep going
>>7966586
Stranger shits have been shat
>>7966685
I would, anon, but I'm no authority. If I ever have anything conclusive to share, I'll try to publish it.
Did you have something you wanted to talk about re: P vs. NP?
>>7966103
You can't even get the recursive property right you fucking idiot.
>>7966005
ive actually already proven it but its too long to fit in this post
>>7966946
Feeeck came here to say that
>inb4
>wrong meme equation
>knock knock this is the meme police mam you're son was an alcohol
>>7966005
I can! I programmed CAS software on my computer to figure out the whole proof for me. It's currently calculating right now, and will give me the proof any second now...
Any second now...
>>7966995
lulz
see you in a graham number of years bro
>>7967000
i'd give you the code so you could test it yourself but i'm afraid there isn't enough room in this comment box to include the whole thing
>>7967003
two for two buh you're killing it
>>7966005
Let's say I decide to solve P=NP problem. How would I go about that? What topics should I learn, what literature should I read? Assume that I have only the very basics of complexity theory and whatnot.
(I a not so naive as to believe that I have a chance of actually solving the problem. But pretending that I have such a goal might be a good way to motivate myself for a while.)
here's the proof:
"who cares"
>>7968262
The only real requirement to work on the problem is knowledge of what the problem means and the different proof methods that are available to you.
This is the easiest approach I know of to do some kind of productive work on the topic:
Pick an NP-complete problem you find to be interesting. Once you find one that you're motivated to explore and that you can easily grasp, try to find a polynomial-time algorithm to solve it.
If you find a provably correct and polynomial-time algorithm, you've proven P = NP. As you develop algorithms, take note of circumstances that are common to all of your most painful edge cases. If you can find a pattern to these circumstances, you may be able to exploit them to determine a lower bound to the upper bound worst-case complexity of the problem in the general case. If you can find a provable super-polynomial lower bound, this is your proof that P != NP.
My advice:
1) Remember that you don't need to stick to this method. Constructive proofs are the most interesting to me, so I'm suggesting that you follow a looser version of my own strategy which I've been developing to be able to admit a constructive proof on purpose.
2) Take everything in context. This problem has stumped many people; don't ignore your life to work on this every time you feel you're close to a breakthrough.
3) Don't forget that you can still produce something important even if you don't prove that P = NP. For example, if you can come up with a low-complexity, high-accuracy approximation algorithm which contradicts approximability results that came as a result of some popular assumption, you can disprove that assumption. On a more practical note, if you come up with an approximation algorithm that offers more than the state of the art in either speed or accuracy, you may be able to offer improvements to systems that depend on your chosen problem.
>>7968580
>This problem has stumped many people;
please tell us more anon
>>7966503
P.
It's just searching a list. O(n).
>>7966281
You retard try taking yourself less seriously next time
yeah one sec
>>7966503
Since every manifestation of this problem deals specifically with the number 9999, finding which number was removed is O(9999) = O(1). So this problem is trivially in P.
Yes.
>>7966281
hello newfriend
oh hey, i remember this from that one episode of elementary, wonder how much that episode got wrong
Can someone, please, explain me, what the fuck are we trying to solve here? What the fuck is this all about? Is it even useful to comprehend? Is it even comprehendable?
It truly feels like we are meming each other all the fucking time.
tl;dr wtf is going on
>>7966005
Let us assume P is any subset of Real non-faggot numbers.
The fact that P=NP can be posted N times a day but still get P number of newfags supports the fact that P=OP for being too effective.
However, we can also substitute a value for NP where NP would be not being any good because P=OP which means NOP so NOT OVER POWERED.
We can deduce that not being over powered results in being oppressed by ones who are over powered that homosexuals in society are not overpowered, thus homosexuals =NP.
Putting this together we get OP=HOMOSEXUAL or colloquially OP=FAGGOT
Please don't hate on my proof, I am an engineer.
>>7969158
No, seriously, what the fuck is this shit?
>>7969160
engineering
>>7969155
It's the halting problem. Turing solved it decades ago but for some reason people still ask it.
>>7966508
it might have been proven to be uncomputable
>>7969155
P=NP essentially boils down to, "if I can confirm it quickly, can I find the answer quickly"
I think the best problem to explain it with is SUBSET-SUM, which takes in 2 inputs, an array of numbers A, and a target number T. We want to know whether or not there exists a subset of A that sums exactly to T. Note that we do not actually need to know the answer, but rather whether one exists. Now, if A has length n, then there are 2^n different subsets which must be checked. But assume you had an all knowing oracle, that gave you an answer in the form of a certificate, essentially an example of a solution. It's quite simple to quickly test whether or not that solution works, simply check all elements in the certificate are in A, and the sum of the certificate equals T. NP means that the question can be confirmed in polynomial time, so for example addition is in NP because its simple to confirm given a certificate. We know P is a subset of NP, but P=NP is whether or not any problem which can be verified in polynomial time (look up time complexity for a more detailed explanation) can be solved in polynomial time.
>>7969259
Don't believe him, it has nothing to do with the halting problem. The halting problem was proven to be uncomputable, AKA no computer (Turing machine) can solve it. P=NP is a question about efficiency, not about computability. There are some questions that computers simply cannot solve for all inputs. We can solve all the problems that are NP, but we just can't do them efficiently.
>>7966281
They aren't the embarrassing ones in this situation.
>>7968262
Sipser, Introduction to the theory of computation
you can find it for free online (libgen)
N = NP
:because
N*N/P+1/3.3332333323333233337 = 0.258976214758412158458749 *0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000015256987458256985417
The proof is GOD.
How do you guys like the movie, though?
I though it was pretty nice.
Does anybody on /sci/ actually do legitimate research in this area?
I'd really like to work on this topic in graduate school, but I also want to have a marketable skill outside of academia.
>>7970053
>but I also want to have a marketable skill
well the proof is worth a million dollars... plus, if you could prove that P=NP, you'd be able to crack anyone's password in polynomial time, so that's a pretty marketable skill
>>7969155
>>7969186
>It's the halting problem
lol no
He's trolling you. It's the question of whether there are any problems that can't be solved in polynomial time. We don't know.
Write an algorithm that solves the traveling salesman problem (or any other equivalent problem currently thought to require exponential time) in polynomial time and you win the prize.
>>7969765
dem legs on the blonde
>>7970066
I'd be happy with any result. If you can devise a constructive proof that P != NP, you could build one-way functions and become the Pokemon master of cryptography.
>>7970086
>It's the question of whether there are any problems that can't be solved in polynomial time. We don't know.
No it isn't. There are certainly problems that could never be solved in polynomial time.
>>7970189
This. There are complexity classes beyond NP.
>>7966014
Typical computer """""""scientists"""""""
I only have a layperson's understanding of this topic, excuse me if this post is retarded.
But what if you developed a program to write programs evolutionarily? Does such a thing exist? I'm having a hard time explaining what I mean, but maybe you guys have heard of boxcar2d, this algorithm that randomly creates assemblages of polygons and wheels and then selects the one that goes the farthest along some simulated terrain as the seed for subsequent generations of vehicles. What if you invented an algorithm that randomly generates algorithms to solve some problems in this way, then uses the one that solves it in the fastest time to generate subsequent algorithms?
If you wrote the algorithm-generating algorithm for a quantum computer, would it create an algorithm that could solve problems on a classical computer?
>>7970716
https://en.wikipedia.org/wiki/Metaheuristic
The issue with progressively generating algorithms is that there is no guarantee for correctness. Even if you could hypothetically generate an algorithm that is correct, proving that it's correct in itself is an NP-complete problem.
https://en.wikipedia.org/wiki/Automated_theorem_proving
