27
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)...
20
Many natural problems can be expressed as Constraint Satisfaction Problems, and there are dichotomy theorems for CSPs.
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 ...
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
Mihalis Yannakakis has shown that the traveling salesman problem cannot be solved in polynomial time by using a symmetric linear program.
See the paper Expressing combinatorial optimization problems by Linear Programs, by Yannakakis.
This result was improved recently by Fiorini, Massar, Pokutta, Tiwary, and De Wolf to drop the "symmetric" requirement in ...
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
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 ...
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#...
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
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 ...
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.5k4 gold badges57 silver badges144 bronze badges
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
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
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
The idea of diagonally running all possible Turing machines has been previously used by Leonid Levin in what is now famously called Levins Universal Search. Unfortunately, and contrary to the extremely common misconception, for what I know variations on Levins universal search are NOT able to provide explicit algorithm solving SAT (decision problem) in ...
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,...
9
Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you're given a circuit for the function.
The paper:
https://eccc.weizmann.ac.il/report/2017/109/
shows that certain counterexamples to BBH would refute a non-...
8
This answer is for your "somewhat related question":
In the following recent paper, Klee-Minty cubes were used explicitly to show that there exists a pivoting rule for the simplex method (not one of the standard ones, like Dantzig's pivoting rule analysed by Disser and Skutella) for which it is PSPACE-complete to decide whether a variable enters the basis ...
8
We can not rule-out a forth possibility that there are plenty of natural $NP$-intermediate problems. The apparent scarcity is due to lack of necessary techniques and tools required to prove $NP$-intermediate status under some plausible complexity conjecture (Arora and Barak noted that we can not prove the $NP$-intermediate status of any natural $NP$ problem ...
answered Feb 8 '14 at 13:24
Mohammad Al-Turkistany
20.5k4 gold badges57 silver badges144 bronze badges
8
Here is a result from descriptive complexity theory:
$P \ne NP$ if and only if some second order property is not expressible using first order logic plus least fixed point.
Reference:
Immerman, Languages that capture complexity classes
answered Jan 21 '15 at 14:57
Mohammad Al-Turkistany
20.5k4 gold badges57 silver badges144 bronze badges
Only top voted, non community-wiki answers of a minimum length are eligible