Formally, What is P and NP?
Moderators: phlip, Moderators General, Prelates

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Formally, What is P and NP?
Iff the problem is P and f(x) is the function that says how long it would take most efficient process to solve this problem, the f(x) can be expressed as a polynomial.
Iff the problem is NP and g(x) is the function that says how long it would take most efficient process to solve this problem, the g(x) cannot be expressed as a not a polynomial.
This is my understanding. The problem I have is what type of function is not a polynomial and how do we know the proportions of such a function.
Iff the problem is NP and g(x) is the function that says how long it would take most efficient process to solve this problem, the g(x) cannot be expressed as a not a polynomial.
This is my understanding. The problem I have is what type of function is not a polynomial and how do we know the proportions of such a function.
Re: Formally, What is P and NP?
1) Your understanding of NP is incorrect. It is "polynomialtime on a nondeterministic Turing machine", not "nonpolynomial". The set of problems in P is a subset of the set of problems in NP. The classic question is, are there any problems in NP that aren't also in P?
2) A typical example of a function that isn't bounded above by any polynomial function is an exponential function, for example f(x)=2^{x}. There is no polynomial function p(x) such that p(x) > 2^{x} for all x>0.
2) A typical example of a function that isn't bounded above by any polynomial function is an exponential function, for example f(x)=2^{x}. There is no polynomial function p(x) such that p(x) > 2^{x} for all x>0.
Re: Formally, What is P and NP?
Wikipedia is right there.
If you need it dumbed down, NP is stuff like Sudoku: if someone shows you a solved Sudoku, you can check whether it is indeed solved without much effort, even if you don't know how to solve it yourself.
If you need it dumbed down, NP is stuff like Sudoku: if someone shows you a solved Sudoku, you can check whether it is indeed solved without much effort, even if you don't know how to solve it yourself.
Zµ«VjÕ«ZµjÖZµ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«ZµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZ
Re: Formally, What is P and NP?
There are two equivalent formulations of NP  the verifier and the machine definition (2.1 and 2.2 on the wikipedia page).
I prefer the machine definition because I think it's pretty quick to intuit: the N in NP stands for nondeterministic, so imagine being able to write computer programs with a special instruction gotok, which allows you to jump to k different points in the program simultaneously and as long as one of those branches returns YES, then the whole program returns YES (otherwise it returns NO).
An example of solving SAT in nondeterministic pseudocode:
this is clearly a polynomial time algorithm, so SAT is in NP
I prefer the machine definition because I think it's pretty quick to intuit: the N in NP stands for nondeterministic, so imagine being able to write computer programs with a special instruction gotok, which allows you to jump to k different points in the program simultaneously and as long as one of those branches returns YES, then the whole program returns YES (otherwise it returns NO).
An example of solving SAT in nondeterministic pseudocode:
Code: Select all
assignments = []
for variable in SAT, gotok(A, B)
A: assignments.append((variable, True))
B: assignments.append((variable, False))
return satisfied(assignments, SAT)
this is clearly a polynomial time algorithm, so SAT is in NP

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Formally, What is P and NP?
The P = NP Problem is to answer the question, "Can a nondeterministic Turning machine solve a puzzle such that a function describing how long it will take the machine to solve the puzzle is not a polynomial?" Iff the answer is yes, then P =/= NP.
Is this correct?
Is this correct?
Re: Formally, What is P and NP?
Not quite, no.
The comparison is between what Nondeterministic machines can do in polynomial time and what deterministic machines can do in polynomial time.
The comparison is between what Nondeterministic machines can do in polynomial time and what deterministic machines can do in polynomial time.

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Formally, What is P and NP?
jewish_scientist wrote:"Can a nondeterministic Turning machine solve a puzzle such that a function describing how long it will take the machine to solve the puzzle is not a polynomial?" Iff the answer is yes, then P =/= NP.
Is this correct?
Here are a two ways of looking at this definition, because no, not really. For example, you are only talking about the runtime of the nondeterministic machine. Or... "what puzzle" are you talking about? There are certainly puzzles that NTMs can solve in polytime, so it can't be "there exists a puzzle such that...". But there are also certainly puzzles that NTMs can not solve in polytime, and provably so; so it can't be "for all puzzles" either. (The solution to this is that it's for all, but you compare the runtime of the best NTM to the best DTM.)
The first definition is the following. Take some puzzle, and consider the fastest (asymptotically) nondeterministic and the fastest deterministic turning machines that can solve that puzzle; let f be the function that describes the runtime of the NTM and g describe the runtime of the DTM. P = NP if, for all puzzles, either both f and g are polynomial or neither is. P != NP if there's some puzzle that can be solved in polytime by an NTM but cannot be solved in polytime by a DTM.
The second definition is the following. Let P be the set of puzzles that can be solved by a DTM in polytime. Let NP be the set of puzzles that can be solved by a NTM in polytime. Well, P = NP just does set comparison on those sets. (Formally, a "puzzle" is a function that produces a Boolean output.)
The two are basically the same (because S = T for sets is defined to be "x ∈ S iff x ∈ T for all possible elements x"), but they're two sides of the same coin so maybe one will "stick" better.
One other way of looking at it is the following. I think this is right, but I'm tired and I've got a nagging feeling I'm getting something wrong.
There are some things you can do to a Turing machine that increase its expressiveness. For example, you can have TM definitions where the tape is infinite in both directions or in just one direction. Or you can have a TM definition that allows multiple tapes. In these cases, it is possible to take a TM that uses that extra expressiveness and convert it into a TM that doesn't (e.g. convert a multitape TM to a singletape TM) such that the runtime of the resulting TM doesn't increase "too much." For this discussion, "too much" means that if the original TM always runs in polytime, then the resulting TM will always run in polytime as well.
Consider nondeterminism as something that increases the expressiveness of a TM. Nondeterministic TMs can be converted to DTMs, but with a catch: it's not known how to do it efficiently. The only known conversions will increase the runtime of the original TM exponentially. If P = NP, then we're missing something, and there is a way to do that conversion and preserve the polynomial runtime of the original. If P != NP, then we're not, and that conversion isn't possible to do in general.
 Xanthir
 My HERO!!!
 Posts: 5291
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Formally, What is P and NP?
Nah, your second definition is fine afaict. Only correction:
This definition doesn't require the original TM to run in polytime, just that when you downgrade to the "lesspowerful" TM, the increase in runtime is described by a polynomial function relative to the input size (rather than an exponential or higher function).
For this discussion, "too much" means that if the original TM always runs in polytime, then the resulting TM will always run in polytime as well.
This definition doesn't require the original TM to run in polytime, just that when you downgrade to the "lesspowerful" TM, the increase in runtime is described by a polynomial function relative to the input size (rather than an exponential or higher function).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Formally, What is P and NP?
Just double checking: If P is a set of the puzzles that a deterministic Turning machine can solve in polynomial time and NP is a set of the puzzles that a nondeterministic Turning machine can solve in polynomial time, then P ⊂ NP.
 Xanthir
 My HERO!!!
 Posts: 5291
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Formally, What is P and NP?
Yes, P by definition is a subset of NP; everything in NP is definitely in P. It's just that "subset" might mean "same set".
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Formally, What is P and NP?
Is this true: If I find the truth value of that really long statement I gave, then I have solved P = NP according to the machine definition of P = NP.
If so, can we talk about the verifier definition of P = NP?
If so, can we talk about the verifier definition of P = NP?
 Xanthir
 My HERO!!!
 Posts: 5291
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Formally, What is P and NP?
What "really long statement"?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Formally, What is P and NP?
If P is a set of the puzzles that a deterministic Turning machine can solve in polynomial time and NP is a set of the puzzles that a nondeterministic Turning machine can solve in polynomial time, then P ⊂ NP.
 Xanthir
 My HERO!!!
 Posts: 5291
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Formally, What is P and NP?
Yes, if you can establish that the "P" set is definitely a proper subset of the "NP" set (or, conversely, that they're the same set), then you've solved the problem.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Formally, What is P and NP?
Thank you all for helping me understand the machine definition of the N = NP problem. Can we now discuss the verifier definition?
 Xanthir
 My HERO!!!
 Posts: 5291
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Formally, What is P and NP?
You can discuss whatever you want, man. Nobody's stopping you.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

 Posts: 263
 Joined: Sun Feb 22, 2015 2:40 pm UTC
Re: Formally, What is P and NP?
jewish_scientist wrote:Thank you all for helping me understand the machine definition of the N = NP problem. Can we now discuss the verifier definition?
The gist of that as I understand it;
If you can verify that any particular solution is correct in polytime, then you can trivially make a brute force NFS that simply tries all possible answers and verifies that at least one of them is correct, in polytime.
Now you just need to show:
1) That anything which can not be verified in polytime, can't be solved by an NFS in polytime.
2) That anything which can be verified in polytime (implying NP) can be solved by a DFS in polytime. (=P)
The first sounds like it is trivial, but the second is obviously super difficult.
 Yakk
 Poster with most posts but no title.
 Posts: 11078
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Formally, What is P and NP?
I dislike the machine definition of NP.
I prefer the proof one.
A problem is in NP if, for every instance of the problem whose answer is "yes", you can write a proof with length polynomial in the size of the problem that proves the answer is "yes". This proof can be reliably checked in polynomial time. This proof can be encoded however you want.
A problem is in P if there is a program that takes instances of the problem, and finds out if the answer is "yes" in polynomial time.
P is a subset of NP because a "proof" consisting of what steps the Pprogram took is a "proof" the answer is "yes".
We can see that the proof based NP definition is the same as the machine based one. If an NDTM solves a problem in NP, that means that for all "yes" answers there is an execution path that leads to the "accept" node.
That execution path is polynomial in length of the original problem (by the machine definition of NP). We can check that the execution path is valid by simply checking each step in the NDTM, ignoring the other branches and always following the execution path are told leads to "accept". If the path does lead to "accept", then the proof is valid.
The other way around, take your proof encoding. Create an NDTM that nondetermistically writes out every proof in that encoding bounded by the polynomial bound of the proofbased NP definition, then checks every proof, and accepts if it finds a valid one.
I find this definition of NP highlights exactly how powerful NP is; anything with a short proof of acceptance is in NP. And P=NP basically means that anything whose proof is easy to check, is easy to solve.
I prefer the proof one.
A problem is in NP if, for every instance of the problem whose answer is "yes", you can write a proof with length polynomial in the size of the problem that proves the answer is "yes". This proof can be reliably checked in polynomial time. This proof can be encoded however you want.
A problem is in P if there is a program that takes instances of the problem, and finds out if the answer is "yes" in polynomial time.
P is a subset of NP because a "proof" consisting of what steps the Pprogram took is a "proof" the answer is "yes".
We can see that the proof based NP definition is the same as the machine based one. If an NDTM solves a problem in NP, that means that for all "yes" answers there is an execution path that leads to the "accept" node.
That execution path is polynomial in length of the original problem (by the machine definition of NP). We can check that the execution path is valid by simply checking each step in the NDTM, ignoring the other branches and always following the execution path are told leads to "accept". If the path does lead to "accept", then the proof is valid.
The other way around, take your proof encoding. Create an NDTM that nondetermistically writes out every proof in that encoding bounded by the polynomial bound of the proofbased NP definition, then checks every proof, and accepts if it finds a valid one.
I find this definition of NP highlights exactly how powerful NP is; anything with a short proof of acceptance is in NP. And P=NP basically means that anything whose proof is easy to check, is easy to solve.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Who is online
Users browsing this forum: Steeler [Crawler] and 6 guests