57
Strassen's statement needs to be put into context. This was an address to an audience of mathematicians in 1986, a time when many mathematicians did not have a high opinion of theoretical computer science. The complete statement is
For some of you it may seem that the theories discussed here rest on weak foundations. They do not. The evidence in favor of ...
26
As others have pointed out, it's debatable to what extent the thing you're trying to explain is even true. One could argue that, in the 60s and 70s, theoretical computer scientists were just more interested in the sorts of problems that turn out to be either in P or else NP-complete. Today, because of the rise of complexity-theoretic cryptography, quantum ...
25
Let me give a toy example of the relativization barrier. The canonical example is the time hierarchy theorem that ${\bf TIME}[t(n)] \subsetneq {\bf TIME}[t(n)^2]$. The proof (by diagonalization) is only a little more involved than the proof that the halting problem is undecidable: we define an algorithm $A(x)$ which simulates the $x$th algorithm $A_x$ on ...
24
As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment)...
22
I recommend Jenga!
Assuming you have two perfectly logical, sober, and dextrous players, Jenga is a perfect-information two-player game, just like Checkers or Go. Suppose the game starts with a stack of $3N$ bricks, with 3 bricks in each level. For most of the game, each player has $\Theta(N)$ choices at each turn for the next move, and in the absence of ...
21
If P=NP, there must be polynomial-time algorithms for NP-complete problems. However, there might not be any algorithm that provably solves an NP-complete problem and provably runs in polynomial time.
20
Your question might better be phrased, "How would complexity theory be affected by the discovery of a proof that P = NP is formally independent of some strong axiomatic system?"
It's a little hard to answer this question in the abstract, i.e., in the absence of seeing the details of the proof. As Aaronson mentions in his paper, proving the independence of ...
20
I can see three related ways to understand the question:
1) Can we we regard $NP \ne P$ as a fundamental principle of computational complexity theory, even before we can prove it?
2) Does the $NP \ne P$ principle extends beyond its narrow mathematical meaning?
3) Does the $NP \ne P$ principle can be regarded as a physical law.
I think that there are ...
20
Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first revisions, second revisions, new counter-examples, further revisions, further counter-examples, and so on.
It would be much better, if the authors were able to ...
18
Here is a possible alternative to a padding argument, based on Schöning's generalization of Ladner's theorem. To understand the argument, you need to have access to this paper (which will unfortunately be behind a pay wall for many):
Uwe Schöning. A uniform approach to obtain diagonal sets in complexity
classes. Theoretical Computer Science 18(1):95-103,...
17
Let me give a summary of my understanding of the motivation for the approach. Be warned that I am fairly new to the concept of Borel determinacy, and not at all an expert in set theory. All mistakes are mine. Also I am not sure reading this is all that much better than reading Gowers' posts.
I think what Gowers has in mind is not a finitary analogue of the ...
17
Many natural problems can be expressed as Constraint Satisfaction Problems, and there are dichotomy theorems for CSPs.
17
I think the answer is yes, even today there is no known natural problem that is a candidate for violating the Isomorphism Conjecture.
The primary reason is that typically natural NP-complete problems are very easily seen to be paddable, which Berman and Hartmanis showed suffices to be isomorphic to SAT. For natural graph-related problems this typically ...
17
If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:
Input: N (integer in binary format)
For I = 1 to N do
begin
if I is a valid encoding of a proof of P = NP in PA (or ZFC)
then halt and accept
End
Reject
Another - less trivial - example that relies on no assumption is the following:
Input: x (boolean ...
16
Adachi, Iwata, and Kasai in a 1984 JACM paper show by reduction that the Cat and $k$-Mice game has an $n^{\Omega(k)}$ time lower bound. The problem is in P for each $k$. The problem is played on a directed graph. The moves consist of the cat and then one of the $k$ mice alternating steps. The mice win if they can land on a designated cheese node ...
16
It seems that this idea is attributed to Levin (It is called optimal search). I believe this fact is well known. A similar algorithm is described in wikipedia for instance, although using the subset sum problem. In this article from scholarpedia you can find several references on the subject, including a pointer to the original algorithm and to some other ...
15
I'd just like to write down some version of a padding argument as described in the comments. I don't see why a gap is needed. We want to show that if NP is not contained in P/poly then there is an NP-intermediate problem not contained in P/poly.
There is an unbounded function $f$ such that SAT does not have circuits of size less than $n^{f(n)}$, and so ...
15
The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true as permanent is complete for both VNP and #P. Indeed, the Boolean part of VNP is essentially just #P/poly (it contains #P/poly and is contained in $\mathsf{FP}^{...
15
To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is mechanics while integration is art", they're not inviting you to formalize "mechanics" and "art" and prove the statement, they're trying to convey a general ...
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, ...
13
Contrary to some claims earlier in this thread, algebrization in the sense of Aaronson & Wigderson is not known to subsume relativization. For example,
$$\tag{$\dagger$}(\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly})\implies \mathsf{NEXP} \not\subset \mathsf{P/poly}$$
is a statement that ...
13
As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.
Other than this, this topic has been discussed at several other places, see https://en.wikipedia.org/wiki/P_versus_NP_problem#...
12
I'm not sure I understand. A physical law (of the kind you indicate) is a mathematical expression of a model (in that example, relativity) that claims to capture reality. A physical law can be proved wrong if the underlying mathematics is incorrect, but it can also be wrong if the underlying model changes (for example, newtonian mechanics). P vs NP is a ...
12
Consider the following algorithm (a variant of Levin's algorithm):
Run the first $n$ algorithms in parallel. Additionally, run in parallel a brute-force algorithm that tries all possible solutions one by one. (Run all algorithms with the same speed.)
Stop when one of the algorithms finds a solution.
Consider two cases (given an input $x$ of length $...
12
The classic result I know of is due to Paul, Pippenger, Szemeredi and Trotter (1983) and separates deterministic from non-deterministic linear time.
Then, there is the more recent result by Fortnow,Lipton, van Melkebeek and Viglas (2004) that was already mentioned. The uniqueness of this result is that it is a time-space tradeoff result, bounding space as ...
12
1) Depending on exactly what was meant, the conclusion in Kaveh's observation can be strengthened from $\mathsf{NP} \subseteq \mathsf{P/poly}$ to $\mathsf{P} = \mathsf{NP}$, essentially using Mahaney's Theorem. That is, if there is an algorithm which solves SAT and runs in time $\leq p(n)$ on all instances of length $n$ except for possibly $q(n)$ such ...
12
For question 1, the BGS construction can be performed in exponential time, so you can construct such $B \in \mathsf{EXP}$.
(For question 2: Sasho Nikolov's answer was originally only for $\mathsf{\Sigma_k P}$-complete languages, and I pointed out that one can also take any $B' \in \mathsf{NP} \cap \mathsf{coNP}$, since $\mathsf{NP}^{\mathsf{NP} \cap \mathsf{...
12
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 ...
11
$P \ne NP$ if and only if worst-case one-way functions exist.
Reference:
Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical
systems theory, 25(3):203–221, 1992.
answered Mar 7 '14 at 14:36
Mohammad Al-Turkistany
19.5k4 gold badges51 silver badges134 bronze badges
11
Here is a one:
Mahaney's Theorem: There is no sparse NP-complete set if and only if $P \ne NP $
(under Karp reduction).
Another one is:
$P \ne NP$ if and only if $P \ne PH$
answered Jan 20 '12 at 15:08
Mohammad Al-Turkistany
19.5k4 gold badges51 silver badges134 bronze badges
Only top voted, non community-wiki answers of a minimum length are eligible
