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
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)...
23
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
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
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
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
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 ...
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
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
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, ...
14
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#...
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
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
A cashier has to return $x$ cents of change to a customer. Given the coins she has available, can she do it and how?
Brute force: consider all possible collections of coins and see if one of them adds up to $x$.
Non-brute force: do it as every cashier does, by dynamic programming.
There are two variants of the problem:
Easy: the cashier has unlimited ...
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
20.3k4 gold badges56 silver badges142 bronze badges
11
For question 2, you can take any $B' \in \mathsf{PH}$ (this means you cannot bring down the $B$ in the BGS result down from $\mathsf{EXP}$ to $\mathsf{PH}$ without resolving the big question).
Clearly for any $B'$, $P \subseteq \mathsf{P}^{B'} \subseteq \mathsf{NP}^{B'}$. Let $B' \in \Sigma_i^{\mathsf{P}}$. Recall that, by the definition of the Polynomial ...
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$)...
9
Just a joke: after thinking about the "SAT gravitational pull" in the Scott Aaronson's nice answer, another metaphore came to my mind: the 3-SAT 2-SAT sandwich !
... but I don't know if the sandwich can be filled with natural ingredients (however I found that it could be filled with some $(2 + \frac{(\log n)^k}{n^2})$-SAT sauce [1] if the Exponential-Time ...
9
Is there a particular style of problem you are looking for, or anything related to a hereditary graph property? Two common types of problems would be
(1) recognition: does a given $G$ have the hereditary property? or
(2) find the largest (induced or not) subgraph $H$ in $G$ having the hereditary property.
As I'm sure you are familiar, (2) is NP-complete (...
9
Given a CSP where all constraints have arity at most $q$ we want to distinguish between the case where everything is satisfiable and the case where at most $1/2^q$ fraction of the constraints are satisfiable, in polynomial time. Here is how this can be done.
First, all predicates used in the CSP must have at least one satisfying assignment (otherwise we ...
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 ...
9
The answer here seems to imply there is a more general result. For this particular case, here is a self contained way to reduce the problem to maximum weight perfect matching. Assume $k$ is even.
Given $G=(L\cup R, E)$, we construct a new graph $G'=(V',E')$ as follows, let $|R|=n$.
Add vertices in $R$ to $V'$.
For each vertex $v \in L$, add vertices $v_1,...
Only top voted, non community-wiki answers of a minimum length are eligible
