P≠NP: Simplicity of Exponential Functions

[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?

 

[jbriggs444]

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

 

[Adel Makram]

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

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.

 

[pwsnafu]

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.

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.

 

[Adel Makram]

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.

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

 

[pwsnafu]

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

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.

 

[Adel Makram]

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.

But I guess this contradicts your definition of NP:

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

.
So how NP which is supposed by definition to be verified in polynomial time, now require exponential time?

 

[pwsnafu]

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?

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.

 

[Adel Makram]

For me it is all about mutual exclusion. Please look at the attached 2x2 table which I just made.

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

If you do so, the verification of the solution in polynomial time will not invalidate that P is mutually exclusive with EXPTIME.

 

[Adel Makram]

Please look at the attached 2x2 table which I just made now.

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

If you do so, it won`t 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 won`t 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.

 

[pwsnafu]

If you do so, it won`t 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 won`t 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.

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.

 

[Adel Makram]

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.

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!

 

[jbriggs444]

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!

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 keⁿ 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 kn^j 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.

 

[Adel Makram]

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 keⁿ 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 kn^j 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.

But keⁿ can not be expressed in a finite terms of kn^j. 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.

NP≠NEXTIMENP

 

[pwsnafu]

But keⁿ can not be expressed in a finite steps of kn^j.

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

Also, if you put "verified" instead of "solvable" in the your statement, then quotes from pwsnafu becomes true.

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$.

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.

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$.

 

[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.

 

[pwsnafu]

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.

Correct.