22
$\begingroup$

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

$\endgroup$
  • 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$ – Jan Johannsen Oct 10 '14 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$ – Dominic van der Zypen Oct 10 '14 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$ – Damiano Mazza Oct 11 '14 at 7:48
  • $\begingroup$ "$\mathbf{N}\neq 1$ and $\mathbf{P}\neq 0$." *rimshot* $\endgroup$ – David Richerby Oct 13 '14 at 18:45
  • 1
    $\begingroup$ Similar question cstheory.stackexchange.com/questions/9806/… $\endgroup$ – Tayfun Pay Oct 21 '14 at 15:46
14
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Iddo Tzameret Oct 11 '14 at 14:18
  • $\begingroup$ @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... $\endgroup$ – Damiano Mazza Oct 11 '14 at 17:37
  • $\begingroup$ @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. $\endgroup$ – Iddo Tzameret Oct 11 '14 at 17:48
  • $\begingroup$ @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? $\endgroup$ – Damiano Mazza Oct 11 '14 at 17:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Jan Johannsen Oct 14 '14 at 14:18
12
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – DukeZhou Jan 10 '18 at 21:23
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What's a polynomial-mapping? Do you mean "polynomial"? Do you mean "polynomial-time computable function"? Something else? $\endgroup$ – D.W. Dec 3 '16 at 9:33
  • 2
    $\begingroup$ 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$. $\endgroup$ – Iddo Tzameret Dec 3 '16 at 14:12
9
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ I think you mean $P/poly \not \supset NP$. The statement $P \neq NP/poly$ already trivially known. $\endgroup$ – Yonatan N Oct 15 '14 at 19:33
  • $\begingroup$ @YonatanN $P\neq NP/poly$ is true? $\endgroup$ – Brout Dec 4 '16 at 10:18
  • $\begingroup$ Yep. Even P/poly is known to contain problems outside of P, like the unary halting problem. $\endgroup$ – Yonatan N Dec 9 '16 at 2:45
  • $\begingroup$ 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." $\endgroup$ – DukeZhou Jan 10 '18 at 21:27
1
$\begingroup$

How about Philip Maymin's

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

$\endgroup$
  • 3
    $\begingroup$ The claims and "proofs" in this paper do not look rigorous, and the arguments seem lacking to me. Did you read this paper? $\endgroup$ – Rahul Savani Oct 11 '14 at 5:52
  • $\begingroup$ 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. $\endgroup$ – R B Oct 11 '14 at 7:55
  • $\begingroup$ @R B: OK, thanks. $\endgroup$ – Rahul Savani Oct 11 '14 at 10:09
  • 5
    $\begingroup$ And it is written in Microsoft Word :/ $\endgroup$ – gigabytes Oct 14 '14 at 11:36
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.