P versus NP problem

Yo dawgs, could you please solve the P versus NP problem for me? thx in advance.

Other urls found in this thread:

cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf
twitter.com/SFWRedditVideos

EDIT:
Nevermind, found the solution on my own.
Mods, please close this thread. thx bye

>tfw scored third highest on the theory of computation final
Felt good.

sent you a dm with the solution :)

P /= NP

There

/setthreadtitle [SOLVED] P versus NP problem
/thread

I have a marvelous solution, but the input field is too small

I still don't fucking understand this though it's glazed over in every course.

Posting because I don't have enough rep to comment yet. I made a breakthrough today and by god I believe I have it. I'm writing up a more formal proof right now and will post my results tomorrow.
[question closed as off topic]

>god
That's your problem

Roughly,
P - problems that can be solved using a polynomial number of operations with respect to their input
NP - problems when given a solution, can be verified in a polynomial number of operations with respect to their inputs whether that solution was correct
=> P = NP? Asks if problems that can be verified in a polynomial number operations with respect to their input can also be solved in a polynomial number of operations with respect to their input.
Replacing polynomial with easy (non-exponential operation problems are considered easy), it essentially asks whether easily verifiable problems are also easily solvable.
From this it should intuitively make sense why most people think P =/= NP.

Yeah. Same thing every time. I still don't understand.

What about it don't you understand?

Take Sudoku as an example.
Checking wether the puzzle is solved is rather easy (you can loop through each row, square and column to check for duplicates).
But finding the solution is not that easy.
This does not mean it is impossible to find the solution, I mean it clearly is.
But there is not any solutions where you can find it with a polynomial set of operations, as in, you cannot predict how many iterations you need to test in order to find the solution (unless you bruteforce every possible solution until you accept the answer).

Soduko is usually a 9x9 board, so the input is fixed and not really a good example, but I think it might be easier for you to grasp.

What about a sorting problem?

A sortable list could be arbitrarily large and arbitrarily disordered, but verifying it only requires reading each item one time (stopping if you find something misordered)

You can sort a list of N elements with algorithms that have O(N) to O(N^2) complexity.
Either is a polynomial that relates to the number of elements.

I am talking about problems where you cannot solve it or where solving it is so difficult you cannot solve it within a reasonable time.
A better example would be something like encryption, but the math is harder to explain, so I went with soduko.

N = 1

I solved it

I'm emailing the FIelds committee as we speak

sent.
;)

Here's an intuition: most instances of a NP-complete problem have a subset of the problem which is solvable in polynomial time. Yet, this subset is always small enough so that its complement is still NP-complete.
Now, consider P = NP. Then it means even the NP-complete subset is also solvable in polynomial time, which seems unlikely, because you would have found that the P subset was actually the whole instance of the problem before. However, this does not constitute by itself a proof, because nothing prevents the NP-complete subset to be proven that is in P through another method that we happen not to be aware of. For the same reason, that makes a proof of "P != NP" really far off.

N = 1

They're mathematics definitions that aren't immediately intuitive. Read chapter 8 in this textbook:

cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf

Wow funny undergrad cs major. First time this joke has ever been funny to me. Thanks much, many laughs.
-user

Well sorting a list is in P because we have a polynomial time algorithm for sorting arbitrary lists. BUT, as you said, verifying it can also be done in polynomial time which means it's an NP problem as well (P is a subset of NP). NP problems are easy to verify, but not solve.

>NP problems are easy to verify, but not solve.

Oops, I contradicted myself. I mean they're not necessarily easy to solve, although they might, if they're in P.

I've written an app for it:

if (p==np){return true}
else{return false}

LMAO YOU GUYS ARE CRACKING ME UP ROFLMAO 100 100 100 100

underrated

P=NP
P-NP=0
P(1-N)=0

P=0

1-N=0
N=1

The N vs NP is not even a math problem, its simply a misunderstanding of the difference between knowing how to solve a problem and knowing the answer. Like someone could discover a simplified way for solving calculus equations that takes only half as many steps as are required now. But either way the answer is the same. So N vs NP is basically a stupid idea that there is a quick answer for everything which is a completely unscientific question. The only thing we do know is that there are answers to everything.

>its simply a misunderstanding of the difference between knowing how to solve a problem and knowing the answer.

The distinction is the very point of the definitions. What are you talking about?

>tfw only three people in class

Completely wrong layman's understanding of the problem, great job

>youre wrong (gives no explanation to backup why Im wrong)
youve said nothing, I would have been more impressed if you could at least thrown an autism meme at me, great job

The distinction is the very point of the definitions.

P=NP

what distinction?

Between whether a problem is in P (easy to solve) or NP (easy to verify).

>The N vs NP is not even a math problem

>Can be solved by finding a function that maps any P problem to it's associated NP problem, proving any particular P problem does not have an associated NP problem, or any NP problem does not have an associated P problem.
>not math

Pick one and only one.

Also, strictly speaking in terms of computation models, NP means "solved in polynomial number of steps (with respect to input) on a non-deterministic Turing machine", which is equivalent to taking every path of computation possible at every iteration. Doing the same thing with a deterministic Turing machine (one path at a time) would take an exponential amount of time.

so P = NP is just the Goedel computability and Turing halting problem which has already been proven as unsolvable

How so?

Basically, proving P=NP is equivalent to proving there exists a deterministic Turing machine which solves a NP-complete problem in polynomial time. That seems counter-intuitive, so the consensus leans towards P≠NP.
However, I can't really see how P vs. NP can be related to the halting problem, since what a non-deterministic Turing machine can do, a deterministic one can do too. A non-deterministic Turing machine that solves a NP-complete problem necessarily halts and the corresponding deterministic machine halts too, just supposedly a magnitude of time later in the case of P≠NP.

install gentoo

if you're having P problems i feel bad for you son, i got NP problems, but a bitch ain't 1

Kode with Klossy :)

Yeah, bitches are polynomial basic.

no, all problems in NP are necessarily decidable, unlike the halting problem.

the quick verifiability is just one "side effect" of NP problems being nondeterministically polynomial, but it is not the distinctive definition.

Furthermore even if P = NP, there are still infinitely many problems that will never, ever have a quick answer. (And by consequence no, there are definitely (infinitely many) problems that have no (computable) answer.)