24

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}$?

Jan Johannsen
  • 4,630
  • 2
  • 33
  • 50
Dominic van der Zypen
  • 905
  • 6
  • 16
  • 4
    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 Oct 10 '14 at 09:05
  • 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 Oct 10 '14 at 09:25
  • 4
    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? – Damiano Mazza Oct 11 '14 at 07:48
  • "$\mathbf{N}\neq 1$ and $\mathbf{P}\neq 0$." *rimshot* – David Richerby Oct 13 '14 at 18:45
  • 1
    Similar question http://cstheory.stackexchange.com/questions/9806/list-of-theorems-stating-that-p-does-not-equal-np-if-and-only-if – Tayfun Pay Oct 21 '14 at 15:46

6 Answers6

14

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, so it implies $\mathsf{P} \neq \mathsf{NP}$.

Martin
  • 131
  • 4
Jan Johannsen
  • 4,630
  • 2
  • 33
  • 50
  • 2
    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 Oct 11 '14 at 14:18
  • @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 Oct 11 '14 at 17:37
  • @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 Oct 11 '14 at 17:48
  • @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 Oct 11 '14 at 17:59
  • @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 Oct 12 '14 at 15:57
  • 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 Oct 14 '14 at 14:13
  • 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. – Jan Johannsen Oct 14 '14 at 14:18
  • 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 Oct 14 '14 at 18:46
  • 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 Oct 14 '14 at 20:01
13

Geometric complexity theory (GCT) (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, 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, 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 (tcs.se)

Community
  • 1
vzn
  • 11,014
  • 2
  • 31
  • 64
  • 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 Jan 10 '18 at 21:23
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.

Iddo Tzameret
  • 1,899
  • 1
  • 19
  • 27
  • What's a polynomial-mapping? Do you mean "polynomial"? Do you mean "polynomial-time computable function"? Something else? – D.W. Dec 03 '16 at 09:33
  • 2
    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 Dec 03 '16 at 14:12
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. 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.

vzn
  • 11,014
  • 2
  • 31
  • 64
1

How about Philip Maymin's

"Markets are efficient if and only if P = NP" claim ?

R B
  • 9,448
  • 5
  • 34
  • 74
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$.

user3483902
  • 1,261
  • 7
  • 13