<p><a href="http://en.wikipedia.org/wiki/Geometric_complexity_theory" rel="noreferrer">Geometric complexity theory (GCT)</a> (also [1]) has not been mentioned yet. its a large ambitious program to connect P vs NP to algebraic geometry. eg a brief synopsis from the survey <a href="http://www.cse.buffalo.edu/faculty/regan/papers/pdf/Reg02MSFD.pdf" rel="noreferrer">Understanding the Mulmuley-Sohoni Approach to P vs. NP</a>, Regan:</p>
<blockquote>
<p>Stability is informally a notion of not being “chaotic,” and has developed into a major branch of algebraic geometry under the guiding influence of D.A. Mumford among others. Ketan Mulmuley and Milind Sohoni [MS02] observe that many questions about complexity classes can be re-cast as questions about the nature of group actions on certain vectors in certain spaces that encode problems in these classes. This survey explains their framework from a lay point of view, and attempts to evaluate whether this approach truly adds new power to attacks on the P. vs. NP question.</p>
</blockquote>
<p>also some synopsis in section &quot;A new hope?&quot; in <a href="http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext" rel="noreferrer">Status of the P vs NP problem</a>, Fortnow (2009)</p>
<blockquote>
<p>Mulmuley and Sohoni have reduced a question about the nonexistence of polynomial-time algorithms for all NP-complete problems to a question about the existence of a polynomial-time algorithm (with certain properties) for a specific problem. This should give us some hope, even in the face of problems (1)–(3).</p>
<p>Nevertheless, Mulmuley believes it will take about 100 years to carry out this program, if it works at all.</p>
</blockquote>
<p>[1] <a href="https://cstheory.stackexchange.com/questions/17610/wikipedia-style-explanation-of-geometric-complexity-theory">Wikipedia-style explanation of Geometric Complexity Theory</a> (tcs.se)</p>

CC BY-SA 3.0
2018-01-10T21:23:26.860Z
Thanks for bringing in GCT!  It seems to touch on my own problem [M], but I hadn't come across it previously.  *"These computational problems can be characterized by their symmetries. The program aims at utilizing these symmetries for proving lower bounds."*
DukeZhou
CC BY-SA 3.0
2014-10-13T03:40:24.463Z
2014-10-13T03:40:24.463Z
2020-06-17T09:38:08.363Z
vzn
<p>there is a somewhat side/more recently studied field of complexity called <em>graph complexity</em> that studies how larger graphs are built out of smaller graphs using AND and OR operations of edges. Jukna has a <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf">nice survey</a>. in particular using units of "star graphs" there is a key theorem, see p20 remark 1.18 (the theorem is technically stronger than below and actually implies $P \ne NP/poly$):</p>

<blockquote>
  <p>We already known (Theorem 1.7) that bipartite $n × m$ graphs G of star complexity
  $Star(G) = 
(nm/ \log n)$ exist; in fact, such are almost all graphs. On
  the other hand, the Strong Magnification Lemma implies that even a lower
  bound of $Star(G) ≥ (2+c)n$ for an arbitrarily small constant $c &gt; 0$ on the star
  complexity of an explicit $n×m$ graph $G$ with $m = o(n)$ would have great consequences
  in circuit complexity: such a graph would give an explicit boolean
  function $f_G$ requiring circuit of exponential (in the number $\log_2 nm$ of variables)
  size! (Recall that, for boolean functions, even super-linear lower bounds
  are not known so far.) In particular, if the graph $G$ is such that the adjacency
  of vertices in $G$ can be determined by a nondeterministic Turing machine running
  in time polynomial in the binary length $log_2 n$ of the codes of vertices,
  then a lower bound
  $Star(G) ≥ (2 + c)n$
  for an arbitrarily small constant $c &gt; 0$ would imply that $P \ne NP$. Thus,
  star complexity of graphs captures one of the most fundamental problems of
  computer science.</p>
</blockquote>

CC BY-SA 3.0
2014-10-15T19:33:45.910Z
I think you mean $P/poly \not \supset NP$. The statement $P \neq NP/poly$ already trivially known.
Yonatan N
CC BY-SA 3.0
2016-12-04T10:18:12.953Z
@YonatanN $P\neq NP/poly$ is true?
Turbo
CC BY-SA 3.0
2016-12-09T02:45:08.773Z
Yep. Even P/poly is known to contain problems outside of P, like the unary halting problem.
Yonatan N
CC BY-SA 3.0
2018-01-10T21:27:11.117Z
Thanks for the Jukna link!  *"Complexity is one of the crucial scientific phenomena of our times. In this chapter
we consider the complexity of graphs."*
DukeZhou
CC BY-SA 3.0
2014-10-10T18:42:37.417Z
2014-10-10T18:42:37.417Z
vzn
<p>The following result by Raz (Elusive Functions and Lower Bounds for Arithmetic
Circuits, STOC'08) is aimed at $VP\neq VNP$ (and not directly $P\neq NP$), but it might be close enough for the OP:</p>

<p>A polynomial-mapping $f:\mathbb F^n \to \mathbb F^m$ is $(s, r)$-elusive, if for every polynomial-mapping $Γ : \mathbb  F^s → \mathbb F^m $ of degree $r$, Image($f$)$\not⊂$ Image($Γ$). </p>

<p>For many settings of the parameters $n, m, s, r$, <em>explicit</em>
constructions of elusive polynomial-mappings imply strong
(up to exponential) lower bounds for general arithmetic circuits. </p>

CC BY-SA 3.0
2016-12-03T09:33:20.890Z
What's a polynomial-mapping?  Do you mean "polynomial"?  Do you mean "polynomial-time computable function"?  Something else?
D.W.
CC BY-SA 3.0
2016-12-03T14:12:16.970Z
It's simply a sequence of $m$ polynomials, each with the same $n$ variables; hence it defines a mapping from $\mathbb{F}^n$ to $\mathbb{F}^m$.
Iddo Tzameret
CC BY-SA 3.0
2014-10-11T14:39:55.920Z
2014-10-11T14:39:55.920Z
Iddo Tzameret
<p>How about Philip Maymin's </p>

<p>"<a href="http://arxiv.org/pdf/1002.2284v2.pdf" rel="nofollow">Markets are efficient if and only if P = NP</a>" claim ?</p>

CC BY-SA 3.0
2014-10-11T05:52:36.473Z
The claims and "proofs" in this paper do not look rigorous, and the arguments seem lacking to me. Did you read this paper?
Rahul Savani
CC BY-SA 3.0
2014-10-11T07:55:16.237Z
I went over it, and I agree that the methodology isn't that convincing, this is why I called it a "claim" rather than a result.
R B
CC BY-SA 3.0
2014-10-14T11:36:50.397Z
And it is written in Microsoft Word :/
Nicola Gigante
CC BY-SA 3.0
2014-10-10T11:57:36.973Z
2014-10-10T11:57:36.973Z
R B
<p>The function analogs of $P$, and $NP$; $FP$, and $FNP$ would be also interesting in their study of the $P$ $=$ $NP$(?) question. While $P$, and $NP$ are decision problems which return $1$ bit yes/no answers, $FP$, and $FNP$ actually return answers($FNP$ verifies answers). We know that $FP$ $=$ $FNP$, iff $P$ $=$ $NP$.  </p>

CC BY-SA 3.0
2014-10-14T15:16:41.490Z
2014-10-14T15:54:29.807Z
2014-10-14T15:54:29.807Z
user3483902
<p>A proof system for propositional logic is called <em>polynomially bounded</em>, if every tautology <span class="math-container">$\varphi$</span> has a proof in the system of length polynomial in the length of <span class="math-container">$\varphi$</span>.</p>
<p>The statement &quot;There is no polynomially bounded propositional proof system&quot; is equivalent to <span class="math-container">$\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$</span> by a <a href="https://doi.org/10.2307/2273702" rel="nofollow noreferrer">classic result of Cook and Reckhow</a>, so it implies <span class="math-container">$\mathsf{P} \neq \mathsf{NP}$</span>.</p>

CC BY-SA 3.0
2014-10-11T14:18:27.613Z
I would think that (by the definition of a propositional proof system for the $\mathsf{coNP}$-complete language of tautologies), the assumption ("There is no proof system for propositional logic in which every tautology $\varphi$ has a proof of polynomial (in the length of $\varphi$) length") is almost identical to assuming $\mathsf{NP}\neq\mathsf{coNP}$; and hence almost identical to assuming $\mathsf{NP}\neq\mathsf{P}$.
Iddo Tzameret
CC BY-SA 3.0
2014-10-11T17:37:48.207Z
@IddoTzameret: but we do need to know that TAUTOLOGY is $\mathsf{coNP}$-complete, right?  And that is not trivial.  I guess this example is just reaffirming the interest of having "natural" complete problems: we may talk about complexity classes without explicitly talking about the machines used to define them (which seems to be what the OP is asking).  Or maybe I misunderstood your comment...
Damiano Mazza
CC BY-SA 3.0
2014-10-11T17:48:31.680Z
@Damiano,  I think the fact that TAUT is coNP-complete is trivial, in the sense that it is implied by its definition and the NP completeness of SAT.
Iddo Tzameret
CC BY-SA 3.0
2014-10-11T17:59:28.827Z
@IddoTzameret, Ok, but you do agree that the $\mathsf{NP}$-completeness of SAT is not trivial, right?  That's essentially what I was saying.  I mean, between the statement "$\mathsf{NP}\neq\mathsf{coNP}$" formulated in terms of Turing-machines and their runtime and the stament "there is no polynomially bounded propositional proof system" I see a non-trivial gap, they definitely don't look "almost identical". That gap is in the completeness of TAUT or SAT, whichever you like, but it's there. Don't you agree?
Damiano Mazza
CC BY-SA 3.0
2014-10-12T15:57:23.680Z
@Damiano,  the OP asks for problems seemingly unrelated to complexity or Turing machines that imply $NP\neq P$. Jan's suggestion is a very good one; I was only arguing that it is directly related to complexity and Turimg machines (by definitions).
Iddo Tzameret
CC BY-SA 3.0
2014-10-14T14:13:37.597Z
I'm confused: i can build a "proof system" by saying, $\varepsilon$ is a proof for $P$ iff $P$ is a tautology. Every proof has length 1 and is therefore polynomially bounded. Don't you need a couple more assumptions on what constitutes a proof?
cody
CC BY-SA 3.0
2014-10-14T14:18:15.127Z
Yes, the property "$p$ is a proof of $\varphi$" must be checkable in polynomial (in $|p|$ and $|\varphi|$) time . And it must be sound and complete, i.e., a formula should have a proof iff it is a tautology.
Jan Johannsen
CC BY-SA 3.0
2014-10-14T18:46:47.947Z
But then the very definition of proof that is being used here is tightly bound up with time complexity, and in particular with the class $\mathsf{P}$...
Joshua Grochow
CC BY-SA 3.0
2014-10-14T20:01:52.503Z
Yes, that's also what Iddo was saying in his comment above. Nevertheless I think it's a natural property to ask of a proof system that proofs should be efficiently checkable.
Jan Johannsen
CC BY-SA 4.0
2014-10-10T11:24:56.323Z
2022-04-25T07:45:14.513Z
2022-04-25T07:45:14.513Z
Jan Johannsen
<p>This is sort of an open-ended question - for which I apologize in advance.</p>

<p>Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the answer of which would imply $\mathbf{P}\neq \mathbf{NP}$?</p>

CC BY-SA 3.0
2014-10-10T09:05:29.977Z
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?
Jan Johannsen
CC BY-SA 3.0
2014-10-10T09:25:07.313Z
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
Dominic van der Zypen
CC BY-SA 3.0
2014-10-11T07:48:58.077Z
I guess [descriptive complexity](http://people.cs.umass.edu/~immerman/descriptive_complexity.html) 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?
Damiano Mazza
CC BY-SA 3.0
2014-10-13T18:45:52.073Z
"$\mathbf{N}\neq 1$ and $\mathbf{P}\neq 0$." \*rimshot\*
David Richerby
CC BY-SA 3.0
2014-10-21T15:46:33.743Z
Similar question http://cstheory.stackexchange.com/questions/9806/list-of-theorems-stating-that-p-does-not-equal-np-if-and-only-if
Tayfun Pay
<cc.complexity-theory><complexity-classes><p-vs-np>
Statements that imply $\mathbf{P}\neq \mathbf{NP}$
Dominic van der Zypen
# Statements that imply $\mathbf{P}\neq \mathbf{NP}$

(Asked by: username_0 on 2014-10-10)

This is sort of an open-ended question - for which I apologize in advance.

Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the answer of which would imply $\mathbf{P}\neq \mathbf{NP}$?

**Tags:** cc.complexity-theory, complexity-classes, p-vs-np

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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  
> **username_2**: I guess [descriptive complexity](http://people.cs.umass.edu/~immerman/descriptive_complexity.html) 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?  
> **username_3**: "$\mathbf{N}\neq 1$ and $\mathbf{P}\neq 0$." \*rimshot\*  
> **username_4**: Similar question http://cstheory.stackexchange.com/questions/9806/list-of-theorems-stating-that-p-does-not-equal-np-if-and-only-if  

---

## 6 answers

### Answer by username_1 on 2014-10-10. Score: 14 | Accepted answer

A proof system for propositional logic is called *polynomially bounded*, if every tautology $\varphi$ has a proof in the system of length polynomial in the length of $\varphi$.

The statement "There is no polynomially bounded propositional proof system" is equivalent to $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$ by a [classic result of Cook and Reckhow](https://doi.org/10.2307/2273702), so it implies $\mathsf{P} \neq \mathsf{NP}$.

> **Comments:**
> **username_9**: I would think that (by the definition of a propositional proof system for the $\mathsf{coNP}$-complete language of tautologies), the assumption ("There is no proof system for propositional logic in which every tautology $\varphi$ has a proof of polynomial (in the length of $\varphi$) length") is almost identical to assuming $\mathsf{NP}\neq\mathsf{coNP}$; and hence almost identical to assuming $\mathsf{NP}\neq\mathsf{P}$.  
> **username_2**: @IddoTzameret: but we do need to know that TAUTOLOGY is $\mathsf{coNP}$-complete, right?  And that is not trivial.  I guess this example is just reaffirming the interest of having "natural" complete problems: we may talk about complexity classes without explicitly talking about the machines used to define them (which seems to be what the OP is asking).  Or maybe I misunderstood your comment...  
> **username_9**: @Damiano,  I think the fact that TAUT is coNP-complete is trivial, in the sense that it is implied by its definition and the NP completeness of SAT.  
> **username_2**: @IddoTzameret, Ok, but you do agree that the $\mathsf{NP}$-completeness of SAT is not trivial, right?  That's essentially what I was saying.  I mean, between the statement "$\mathsf{NP}\neq\mathsf{coNP}$" formulated in terms of Turing-machines and their runtime and the stament "there is no polynomially bounded propositional proof system" I see a non-trivial gap, they definitely don't look "almost identical". That gap is in the completeness of TAUT or SAT, whichever you like, but it's there. Don't you agree?  
> **username_9**: @Damiano,  the OP asks for problems seemingly unrelated to complexity or Turing machines that imply $NP\neq P$. Jan's suggestion is a very good one; I was only arguing that it is directly related to complexity and Turimg machines (by definitions).  
> **username_15**: I'm confused: i can build a "proof system" by saying, $\varepsilon$ is a proof for $P$ iff $P$ is a tautology. Every proof has length 1 and is therefore polynomially bounded. Don't you need a couple more assumptions on what constitutes a proof?  
> **username_1**: Yes, the property "$p$ is a proof of $\varphi$" must be checkable in polynomial (in $|p|$ and $|\varphi|$) time . And it must be sound and complete, i.e., a formula should have a proof iff it is a tautology.  
> **username_16**: But then the very definition of proof that is being used here is tightly bound up with time complexity, and in particular with the class $\mathsf{P}$...  
> **username_1**: Yes, that's also what Iddo was saying in his comment above. Nevertheless I think it's a natural property to ask of a proof system that proofs should be efficiently checkable.  

---

### Answer by username_5 on 2014-10-13. Score: 13

[Geometric complexity theory (GCT)](http://en.wikipedia.org/wiki/Geometric_complexity_theory) (also [1]) has not been mentioned yet. its a large ambitious program to connect P vs NP to algebraic geometry. eg a brief synopsis from the survey [Understanding the Mulmuley-Sohoni Approach to P vs. NP](http://www.cse.buffalo.edu/faculty/regan/papers/pdf/Reg02MSFD.pdf), Regan:

> Stability is informally a notion of not being “chaotic,” and has developed into a major branch of algebraic geometry under the guiding influence of D.A. Mumford among others. Ketan Mulmuley and Milind Sohoni [MS02] observe that many questions about complexity classes can be re-cast as questions about the nature of group actions on certain vectors in certain spaces that encode problems in these classes. This survey explains their framework from a lay point of view, and attempts to evaluate whether this approach truly adds new power to attacks on the P. vs. NP question.

also some synopsis in section "A new hope?" in [Status of the P vs NP problem](http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext), Fortnow (2009)

> Mulmuley and Sohoni have reduced a question about the nonexistence of polynomial-time algorithms for all NP-complete problems to a question about the existence of a polynomial-time algorithm (with certain properties) for a specific problem. This should give us some hope, even in the face of problems (1)–(3).
>
> Nevertheless, Mulmuley believes it will take about 100 years to carry out this program, if it works at all.

[1] [Wikipedia-style explanation of Geometric Complexity Theory](https://cstheory.stackexchange.com/questions/17610/wikipedia-style-explanation-of-geometric-complexity-theory) (tcs.se)

> **Comments:**
> **username_6**: Thanks for bringing in GCT!  It seems to touch on my own problem [M], but I hadn't come across it previously.  *"These computational problems can be characterized by their symmetries. The program aims at utilizing these symmetries for proving lower bounds."*  

---

### Answer by username_9 on 2014-10-11. Score: 10

The following result by Raz (Elusive Functions and Lower Bounds for Arithmetic
Circuits, STOC'08) is aimed at $VP\neq VNP$ (and not directly $P\neq NP$), but it might be close enough for the OP:

A polynomial-mapping $f:\mathbb F^n \to \mathbb F^m$ is $(s, r)$-elusive, if for every polynomial-mapping $Γ : \mathbb F^s → \mathbb F^m $ of degree $r$, Image($f$)$\not⊂$ Image($Γ$).

For many settings of the parameters $n, m, s, r$, *explicit*
constructions of elusive polynomial-mappings imply strong
(up to exponential) lower bounds for general arithmetic circuits.

> **Comments:**
> **username_10**: What's a polynomial-mapping?  Do you mean "polynomial"?  Do you mean "polynomial-time computable function"?  Something else?  
> **username_9**: It's simply a sequence of $m$ polynomials, each with the same $n$ variables; hence it defines a mapping from $\mathbb{F}^n$ to $\mathbb{F}^m$.  

---

### Answer by username_5 on 2014-10-10. Score: 9

there is a somewhat side/more recently studied field of complexity called *graph complexity* that studies how larger graphs are built out of smaller graphs using AND and OR operations of edges. Jukna has a [nice survey](http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf). in particular using units of "star graphs" there is a key theorem, see p20 remark 1.18 (the theorem is technically stronger than below and actually implies $P \ne NP/poly$):

> We already known (Theorem 1.7) that bipartite $n × m$ graphs G of star complexity
> $Star(G) =
> (nm/ \log n)$ exist; in fact, such are almost all graphs. On
> the other hand, the Strong Magnification Lemma implies that even a lower
> bound of $Star(G) ≥ (2+c)n$ for an arbitrarily small constant $c > 0$ on the star
> complexity of an explicit $n×m$ graph $G$ with $m = o(n)$ would have great consequences
> in circuit complexity: such a graph would give an explicit boolean
> function $f\_G$ requiring circuit of exponential (in the number $\log\_2 nm$ of variables)
> size! (Recall that, for boolean functions, even super-linear lower bounds
> are not known so far.) In particular, if the graph $G$ is such that the adjacency
> of vertices in $G$ can be determined by a nondeterministic Turing machine running
> in time polynomial in the binary length $log\_2 n$ of the codes of vertices,
> then a lower bound
> $Star(G) ≥ (2 + c)n$
> for an arbitrarily small constant $c > 0$ would imply that $P \ne NP$. Thus,
> star complexity of graphs captures one of the most fundamental problems of
> computer science.

> **Comments:**
> **username_7**: I think you mean $P/poly \not \supset NP$. The statement $P \neq NP/poly$ already trivially known.  
> **username_8**: @YonatanN $P\neq NP/poly$ is true?  
> **username_7**: Yep. Even P/poly is known to contain problems outside of P, like the unary halting problem.  
> **username_6**: Thanks for the Jukna link!  *"Complexity is one of the crucial scientific phenomena of our times. In this chapter we consider the complexity of graphs."*  

---

### Answer by username_11 on 2014-10-10. Score: 1

How about Philip Maymin's

"[Markets are efficient if and only if P = NP](http://arxiv.org/pdf/1002.2284v2.pdf)" claim ?

> **Comments:**
> **username_12**: The claims and "proofs" in this paper do not look rigorous, and the arguments seem lacking to me. Did you read this paper?  
> **username_11**: I went over it, and I agree that the methodology isn't that convincing, this is why I called it a "claim" rather than a result.  
> **username_13**: And it is written in Microsoft Word :/  

---

### Answer by username_14 on 2014-10-14. Score: 0

The function analogs of $P$, and $NP$; $FP$, and $FNP$ would be also interesting in their study of the $P$ $=$ $NP$(?) question. While $P$, and $NP$ are decision problems which return $1$ bit yes/no answers, $FP$, and $FNP$ actually return answers($FNP$ verifies answers). We know that $FP$ $=$ $FNP$, iff $P$ $=$ $NP$.


---

