# P≠NP that simple?

1. Jun 28, 2015

### Adel Makram

If exponential functions are transcendental functions, then they can not be expressed in a polynomial algebraic form. If so, then P≠NP. Is that so simple?

2. Jun 28, 2015

### jbriggs444

No. It is not that simple. Can you please elaborate for us in your words what the question P=NP means?

3. Jun 28, 2015

### Adel Makram

P means means the processing time of a computer algorithm is represented by a polynomial function of time.
NP means processing time of a computer algorithm is represented by an exponential function of time.

4. Jun 28, 2015

### pwsnafu

No, P is the class of all mathematical problems which can be solved by an algorithm which runs in polynomial time.
NP is the class of all mathematical problems whose solution can be verified by an algorithm which runs in polynomial time.

5. Jun 28, 2015

### Adel Makram

However, the solution of all mathematical problems in NP class are solved by an algorithm which runs in exponential time, isn't it?

6. Jun 28, 2015

### pwsnafu

Yes, but we don't know if the converse is true. There may be problems which can be solved in exponential time whose solution verification also require exponential time.

7. Jun 29, 2015

### Adel Makram

But I guess this contradicts your definition of NP:
.
So how NP which is supposed by definition to be verified in polynomial time, now require exponential time?

8. Jun 29, 2015

### pwsnafu

No it doesn't. There's the class P (solvable in polynomial time). There is NP (verifiable in polynomial time). There is EXPTIME (solvable in exponential time). And lastly NEXPTIME (verifiable in exponential time). We know that
$P \subset NP \subset EXPTIME \subset NEXPTIME$
and also that $P \neq EXTIME$and $NP \neq NEXTIME$. At least one of the inclusions is strict, we don't know which one.

If I pick a problem from EXPTIME the solution might be verifiable in polynomial time, or maybe not. It could be true that $NP = EXPTIME$, in which case your definition is fine. But we don't know that.

Last edited: Jun 29, 2015
9. Jun 29, 2015

### Adel Makram

For me it is all about mutual exclusion. Please look at the attached 2x2 table which I just made.
If you do so, the verification of the solution in polynomial time will not invalidate that P is mutually exclusive with EXPTIME.

#### Attached Files:

• ###### NP=P.png
File size:
35.6 KB
Views:
65
10. Jun 29, 2015

### Adel Makram

Please look at the attached 2x2 table which I just made now.
If you do so, it wont invalidate that both P and EXPTIME are mutually exclusive. So if the problem is solvable in exponential time (EXPTIME) but verified in polynomial (NP), it wont be transformed one day to be solvable in polynomial (P) because it can`t be solvable in polynomial and exponential time at the same time.

#### Attached Files:

• ###### NP=P.png
File size:
35.6 KB
Views:
64
11. Jun 29, 2015

### pwsnafu

I have no idea what you are arguing now. "Mutually exclusive" means both cannot be true at the same time, i.e. there does not exist a problem which is both in P and in EXPTIME. That's nonsense, every problem in P is also in EXPTIME.

12. Jun 29, 2015

### Adel Makram

Good starting point now, so how come that every problem in P is a problem in EXPTIME? This again bring us back to the first post, that exponential function is transcendental ones!

13. Jun 29, 2015

### jbriggs444

A problem class is solvable in "exponential time" if the solution to every problem in that class whose size is n takes no more than ken steps for some constant k.

A problem class is solvable in "polynomial time" if the solution to every problem in that class whose size is n takes no more than knj for some constants k and j.

Note that the number of steps required to solve a particular problem in a particular class is always an integer. It is never transcendental.

14. Jun 29, 2015

### Adel Makram

But ken can not be expressed in a finite terms of knj. Also, if you put "verified" instead of "solvable" in the your statement, then quotes from pwsnafu becomes true. namely, the solution of a problem which can be verified in a polynomial time can not be verified in exponential time, if i understood i correctly.

Last edited: Jun 29, 2015
15. Jun 29, 2015

### pwsnafu

So? Exponentials grow faster than any $n^j$ (provided j is fixed). That's all that matters.

The statements you quoted are true. It's called the time heirachy theorem.
We know that $P \neq EXPTIME$ and $NP \neq NEXPTIME$.
We don't known if $P \neq NP$ or if $NP \neq EXPTIME$.

You did not understand correctly. $NP \neq NEXPTIME$ means that there exists at least one problem which can be verified in exponential time but not in polynomial time. Remember, $NP \subset NEXPTIME$.

Last edited: Jun 29, 2015
16. Jun 29, 2015

### Adel Makram

OK that is more clear for me now. So if we can prove that there exists at least one problem which is solvable in exponential time but can not be verified in polynomial time, then we prove that NP≠EXPTIME.

17. Jun 29, 2015

### pwsnafu

Correct.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook