Timeline for Statements that imply $\mathbf{P}\neq \mathbf{NP}$
Current License: CC BY-SA 3.0
Post Revisions
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2016 at 13:11 | history | edited | Jan Johannsen |
edited tags
|
|
| Nov 11, 2015 at 16:24 | vote | accept | Dominic van der Zypen | ||
| Oct 21, 2014 at 15:46 | comment | added | Tayfun Pay | Similar question cstheory.stackexchange.com/questions/9806/… | |
| Oct 19, 2014 at 16:25 | history | tweeted | twitter.com/#!/StackCSTheory/status/523872469984505856 | ||
| Oct 14, 2014 at 15:16 | answer | added | user3483902 | timeline score: 0 | |
| Oct 13, 2014 at 18:45 | comment | added | David Richerby | "$\mathbf{N}\neq 1$ and $\mathbf{P}\neq 0$." *rimshot* | |
| Oct 13, 2014 at 9:58 | history | edited | Dominic van der Zypen | CC BY-SA 3.0 |
added 1 character in body
|
| Oct 13, 2014 at 3:40 | answer | added | vzn | timeline score: 13 | |
| Oct 11, 2014 at 14:39 | answer | added | Iddo Tzameret | timeline score: 10 | |
| Oct 11, 2014 at 7:48 | comment | added | Damiano Mazza | I guess descriptive complexity gives a few examples. For instance, the statment "there are properties (of ordered structures) expressible by second order existential formulas which may not be expressed by second order universal formulas" is equivalent to @JanJohannsen's answer, whereas "there are properties (of ordered structures) expressible by second order existential formulas which may not be expressed by first order formulas with a least fixed point operator" is precisely $\mathsf P\neq\mathsf{NP}$. Do these count? | |
| Oct 10, 2014 at 23:53 | history | edited | Kaveh | CC BY-SA 3.0 |
edited title
|
| Oct 10, 2014 at 18:42 | answer | added | vzn | timeline score: 9 | |
| Oct 10, 2014 at 18:31 | history | edited | vzn |
edited tags
|
|
| Oct 10, 2014 at 11:57 | answer | added | R B | timeline score: 1 | |
| Oct 10, 2014 at 11:24 | answer | added | Jan Johannsen | timeline score: 14 | |
| Oct 10, 2014 at 9:44 | history | edited | Dominic van der Zypen | CC BY-SA 3.0 |
edited title
|
| Oct 10, 2014 at 9:25 | comment | added | Dominic van der Zypen | As there are no "exact" answers to my question, your conjecture would count... I'm just looking for surprising and different angles on the P vs NP problem | |
| Oct 10, 2014 at 9:05 | comment | added | Jan Johannsen | Would "There is no proof system for propositional logic in which every tautology $\varphi$ has a proof of polynomial (in the length of $\varphi$) length." count, or is that too close to complexity due to the polynomial bound? | |
| Oct 10, 2014 at 8:55 | review | First posts | |||
| Oct 10, 2014 at 9:04 | |||||
| Oct 10, 2014 at 8:50 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |