P≠NP: Simplicity of Exponential Functions

  • Context: Graduate 
  • Thread starter Thread starter Adel Makram
  • Start date Start date
Click For Summary

Discussion Overview

The discussion centers around the complexity classes P and NP, particularly exploring the implications of exponential functions being transcendental and their relationship to polynomial time algorithms. Participants examine definitions, relationships, and the nuances of problem-solving and verification times in computational theory.

Discussion Character

  • Debate/contested
  • Technical explanation
  • Mathematical reasoning

Main Points Raised

  • Some participants assert that if exponential functions are transcendental, then P≠NP, suggesting a straightforward conclusion.
  • Others challenge this simplicity, asking for clarification on the definitions of P and NP, emphasizing that P is the class of problems solvable in polynomial time and NP is the class of problems whose solutions can be verified in polynomial time.
  • There is a discussion about the possibility that problems in NP may require exponential time for verification, which raises questions about the definitions of these classes.
  • Some participants propose that the existence of problems in EXPTIME (solvable in exponential time) complicates the relationship between P and NP, suggesting that NP could equal EXPTIME.
  • A later reply points out that every problem in P is also in EXPTIME, which contradicts the idea of mutual exclusivity between these classes.
  • Participants discuss the implications of the time hierarchy theorem, noting that while P and NP are not known to be equal, NP is a subset of NEXPTIME.
  • There is a suggestion that proving the existence of a problem solvable in exponential time but not verifiable in polynomial time would demonstrate that NP≠EXPTIME.

Areas of Agreement / Disagreement

Participants do not reach a consensus; there are multiple competing views regarding the definitions and relationships between P, NP, EXPTIME, and NEXPTIME. The discussion remains unresolved with ongoing debate about the implications of these relationships.

Contextual Notes

Participants express uncertainty about the definitions and relationships between complexity classes, particularly regarding the implications of transcendental functions and the conditions under which problems can be solved or verified in polynomial or exponential time.

Adel Makram
Messages
632
Reaction score
15
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?
 
Mathematics news on Phys.org
No. It is not that simple. Can you please elaborate for us in your words what the question P=NP means?
 
jbriggs444 said:
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.
 
Adel Makram said:
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.
 
pwsnafu said:
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?
 
Adel Makram said:
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.
 
pwsnafu said:
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:
pwsnafu said:
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?
 
Adel Makram said:
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.
 
Last edited:
For me it is all about mutual exclusion. Please look at the attached 2x2 table which I just made.
pwsnafu said:
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.
 

Attachments

  • NP=P.png
    NP=P.png
    29.2 KB · Views: 485
  • #10
Please look at the attached 2x2 table which I just made now.
pwsnafu said:
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.
 

Attachments

  • NP=P.png
    NP=P.png
    29.2 KB · Views: 479
  • #11
Adel Makram said:
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.
 
  • #12
pwsnafu said:
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!
 
  • #13
Adel Makram said:
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 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
jbriggs444 said:
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.
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.
pwsnafu said:
NP≠NEXTIMENP
 
Last edited:
  • #15
Adel Makram said:
But ken can not be expressed in a finite steps of knj.

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##.
 
Last edited:
  • Like
Likes   Reactions: Adel Makram
  • #16
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
Adel Makram said:
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.
 

Similar threads

Undergrad Elementary Functions - What Is The Exact Definition?
  • · Replies 8 ·
Replies
8
Views
3K
Graduate P vs NP undecidable consequences
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Fitness function for window length of filter
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Is e^pi a unique transcendental, or perhaps not transcendental?
  • · Replies 1 ·
Replies
1
Views
2K
Graduate P=NP: New Proof in Book from World Scientific
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Are electrons universal problem solvers?
  • · Replies 4 ·
Replies
4
Views
1K
Graduate Show positivity and boundedness of a non-linear system
  • · Replies 2 ·
Replies
2
Views
1K
Graduate Will P Ever Equal NP as Technology Advances?
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad NP vs P - difference between veryfing and answering
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad What type is a polynomial function?
  • · Replies 7 ·
Replies
7
Views
2K