Page 1 of 1

Formally, What is P and NP?

Posted: Fri Apr 20, 2018 3:06 pm UTC
by jewish_scientist
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.

Re: Formally, What is P and NP?

Posted: Fri Apr 20, 2018 4:50 pm UTC
by DavidSh
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.

Re: Formally, What is P and NP?

Posted: Fri Apr 20, 2018 10:48 pm UTC
by notzeb
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.

Re: Formally, What is P and NP?

Posted: Sat Apr 21, 2018 11:29 am UTC
by >-)
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

Re: Formally, What is P and NP?

Posted: Fri Apr 27, 2018 2:11 pm UTC
by jewish_scientist
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?

Re: Formally, What is P and NP?

Posted: Fri Apr 27, 2018 3:39 pm UTC
by DavidSh
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.

Re: Formally, What is P and NP?

Posted: Fri Apr 27, 2018 6:13 pm UTC
by jewish_scientist
What is being compared?

Re: Formally, What is P and NP?

Posted: Sat Apr 28, 2018 6:02 am UTC
by EvanED
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.

Re: Formally, What is P and NP?

Posted: Sun Apr 29, 2018 7:46 pm UTC
by Xanthir
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).

Re: Formally, What is P and NP?

Posted: Tue May 01, 2018 3:16 pm UTC
by jewish_scientist
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.

Re: Formally, What is P and NP?

Posted: Wed May 02, 2018 4:02 am UTC
by Xanthir
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".

Re: Formally, What is P and NP?

Posted: Wed May 02, 2018 3:21 pm UTC
by jewish_scientist
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?

Re: Formally, What is P and NP?

Posted: Wed May 02, 2018 4:33 pm UTC
by Xanthir
What "really long statement"?

Re: Formally, What is P and NP?

Posted: Fri May 04, 2018 12:36 pm UTC
by jewish_scientist
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.

Re: Formally, What is P and NP?

Posted: Fri May 04, 2018 7:25 pm UTC
by Xanthir
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.

Re: Formally, What is P and NP?

Posted: Wed May 09, 2018 3:06 pm UTC
by jewish_scientist
Thank you all for helping me understand the machine definition of the N = NP problem. Can we now discuss the verifier definition?

Re: Formally, What is P and NP?

Posted: Wed May 09, 2018 6:20 pm UTC
by Xanthir
You can discuss whatever you want, man. Nobody's stopping you.

Re: Formally, What is P and NP?

Posted: Thu May 10, 2018 5:56 pm UTC
by SuicideJunkie
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.

Re: Formally, What is P and NP?

Posted: Tue Jul 31, 2018 3:37 pm UTC
by Yakk
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 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.