Skip to main content
Theoretical Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

5
  • 4
    $\begingroup$ 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? $\endgroup$ Commented Oct 10, 2014 at 9:05
  • $\begingroup$ 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 $\endgroup$ Commented Oct 10, 2014 at 9:25
  • 4
    $\begingroup$ 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? $\endgroup$ Commented Oct 11, 2014 at 7:48
  • $\begingroup$ "$\mathbf{N}\neq 1$ and $\mathbf{P}\neq 0$." *rimshot* $\endgroup$ Commented Oct 13, 2014 at 18:45
  • 1
    $\begingroup$ Similar question cstheory.stackexchange.com/questions/9806/… $\endgroup$ Commented Oct 21, 2014 at 15:46