Formally, What is P and NP?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

jewish_scientist
Posts: 958
Joined: Fri Feb 07, 2014 3:15 pm UTC

Formally, What is P and NP?

Postby jewish_scientist » Fri Apr 20, 2018 3:06 pm UTC

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.
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

DavidSh
Posts: 159
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Formally, What is P and NP?

Postby DavidSh » Fri Apr 20, 2018 4:50 pm UTC

1) Your understanding of NP is incorrect. It is "polynomial-time on a non-deterministic Turing machine", not "non-polynomial". 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)=2x. There is no polynomial function p(x) such that p(x) > 2x for all x>0.

User avatar
notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Re: Formally, What is P and NP?

Postby notzeb » Fri Apr 20, 2018 10:48 pm UTC

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.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Formally, What is P and NP?

Postby >-) » Sat Apr 21, 2018 11:29 am UTC

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 non-deterministic, so imagine being able to write computer programs with a special instruction goto-k, 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, goto-k(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

jewish_scientist
Posts: 958
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Formally, What is P and NP?

Postby jewish_scientist » Fri Apr 27, 2018 2:11 pm UTC

The P = NP Problem is to answer the question, "Can a non-deterministic 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?
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

DavidSh
Posts: 159
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Formally, What is P and NP?

Postby DavidSh » Fri Apr 27, 2018 3:39 pm UTC

Not quite, no.

The comparison is between what Non-deterministic machines can do in polynomial time and what deterministic machines can do in polynomial time.

jewish_scientist
Posts: 958
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Formally, What is P and NP?

Postby jewish_scientist » Fri Apr 27, 2018 6:13 pm UTC

What is being compared?
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Formally, What is P and NP?

Postby EvanED » Sat Apr 28, 2018 6:02 am UTC

jewish_scientist wrote:"Can a non-deterministic 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) non-deterministic 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 multi-tape TM to a single-tape 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.

User avatar
Xanthir
My HERO!!!
Posts: 5336
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Formally, What is P and NP?

Postby Xanthir » Sun Apr 29, 2018 7:46 pm UTC

Nah, your second definition is fine afaict. Only correction:

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 "less-powerful" 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)))

jewish_scientist
Posts: 958
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Formally, What is P and NP?

Postby jewish_scientist » Tue May 01, 2018 3:16 pm UTC

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 non-deterministic Turning machine can solve in polynomial time, then P ⊂ NP.
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

User avatar
Xanthir
My HERO!!!
Posts: 5336
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Formally, What is P and NP?

Postby Xanthir » Wed May 02, 2018 4:02 am UTC

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

jewish_scientist
Posts: 958
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Formally, What is P and NP?

Postby jewish_scientist » Wed May 02, 2018 3:21 pm UTC

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?
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

User avatar
Xanthir
My HERO!!!
Posts: 5336
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Formally, What is P and NP?

Postby Xanthir » Wed May 02, 2018 4:33 pm UTC

What "really long statement"?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

jewish_scientist
Posts: 958
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Formally, What is P and NP?

Postby jewish_scientist » Fri May 04, 2018 12:36 pm UTC

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 non-deterministic Turning machine can solve in polynomial time, then P ⊂ NP.
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

User avatar
Xanthir
My HERO!!!
Posts: 5336
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Formally, What is P and NP?

Postby Xanthir » Fri May 04, 2018 7:25 pm UTC

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

jewish_scientist
Posts: 958
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Formally, What is P and NP?

Postby jewish_scientist » Wed May 09, 2018 3:06 pm UTC

Thank you all for helping me understand the machine definition of the N = NP problem. Can we now discuss the verifier definition?
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

User avatar
Xanthir
My HERO!!!
Posts: 5336
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Formally, What is P and NP?

Postby Xanthir » Wed May 09, 2018 6:20 pm UTC

You can discuss whatever you want, man. Nobody's stopping you.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

SuicideJunkie
Posts: 345
Joined: Sun Feb 22, 2015 2:40 pm UTC

Re: Formally, What is P and NP?

Postby SuicideJunkie » Thu May 10, 2018 5:56 pm UTC

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.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11092
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Formally, What is P and NP?

Postby Yakk » Tue Jul 31, 2018 3:37 pm UTC

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. *Finding* the proof isn't your problem, just verifying any proof handed to you, and knowing one must exist if the answer is "yes".

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 P-program 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 non-determistically writes out every proof in that encoding bounded by the polynomial bound of the proof-based 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.
Last edited by Yakk on Tue Sep 18, 2018 6:55 pm UTC, edited 2 times in total.
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.

Daniellossett
Posts: 1
Joined: Thu Sep 06, 2018 9:37 am UTC

Re: Formally, What is P and NP?

Postby Daniellossett » Sat Sep 15, 2018 12:49 pm UTC

NP : if you have an answer to such a problem, you can “quickly” verify it

P : if you have such a problem you can “quickly” solve it

P = NP : if you have a way to navigate to any solutions that you can check you know you can solve them all.

The importance is that there are no sneaky problems or exceptions once you know this equivalency is true. Many problems that appeared tough will now be solvable. If you know this before any one else you could probably make a lot of profit from it. There are still many problems that are still not generally “quickly” solvable.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 5 guests