I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes.
What I know so far:
- $P \subseteq EXP$ (from Time Hierarchy Theorem )
We don't know an exact relation between $P$ and $NP$, and between $NP$ and $EXPTIME$. What do we know:
2.1 $\forall problem \in P \Rightarrow problem \in NP$ (Any problem in $P$ is in $NP$.)
2.2 $\forall problem \in P \Rightarrow problem \in EXPTIME$ (Any problem in $P$ is in $EXPTIME$.)
In $P$ vs $NP$:
3.1 We haven't found an $ NP $ $complete$ $problem $ that we can solve in polynomial time (this would imply $P = NP$)
3.2 We haven't found a proof that states that we can't find an polynomial (running time) algorithm for an $NP$ $complete$ $problem$ (this would imply $P \neq NP$)
3.3 From 3.1 and 3.2 we can't state anything about the cardinality of $NP-P$. Most of scientists belive that $P \neq NP$ so there are $NP$ problems that we can't solve in polynomial time.
First, if you find and "hole" in what is stated above, please correct me.
Now for my questions:
A. What can we say about $NP$ vs $EXPTIME$? Are there $EXPTIME$ $complete$ problems not in $NP$? For me it sounds like the $P$ vs $NP$ problem just one "level" (in the hierarchy) higher.
B. How does one go about finding a proof like in 3.2? Obviously we haven't found such a proof but I am looking to understand. The first idea that comes to mind is to go with a proof by contradiction. Not finding such a proof doesn't say much (maybe we are not "smart" enough). What else could we try? The problem reduces, in my opinion, to proving that an algorithm in "elegant" (in running time; that means that it is "the fastests")
Kind of bonus question:
C. How does this relate to Godel's incompleteness theorem? Maybe the better question (quite outside of the scope of the original question) is how much of the math we use on answering these questions can be considered a formal system(so we can apply Godel's result)? What parts are not "formal"?
D. I wasn't able (yet) to look very far into . If possible, can someone give me an informal insight on how it handles defining a strict lower (time) bound for a certain problem?