103
votes
Accepted
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
As noted here before, Tardos' example clearly refutes the proof; it gives a monotone function, which agrees with CLIQUE on T0 and T1, but which lies in P. This would not be possible if the proof were ...
- 1,046
94
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
I am familiar with Alexander Razborov whose previous work is extremely crucial and serves as a foundation for Blum's proof. I had the good luck of meeting him today and wasted no time in asking for ...
- 711
41
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
This is posted as community answer because (a) it's not my own words, but a citation from Luca Trevisan on a social media platform or from other people with no CSTheory.SE account; and (b) anyone ...
35
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
The correctness of the claimed proof is being discussed at Luca Trevisan's blog: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/
In particular "...
- 1,047
29
votes
Accepted
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
The following is an obvious consequence:
$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ would imply $\mathsf{L} \subsetneq \mathsf{P}$ and therefore $\mathsf{L} \neq \mathsf{P}$.
By the space ...
- 566
28
votes
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
$
\newcommand{\DSPACE}{\mathsf{DSPACE}}
\newcommand{\L}{\mathsf{L}}
\newcommand{\P}{\mathsf{P}}
\newcommand{\DTIME}{\mathsf{DTIME}}
$
$\L^2 \subseteq \P$ would refute the Exponential Time Hypothesis.
...
- 2,281
26
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some ...
- 306
26
votes
Accepted
Has parameterized complexity led to better algorithms?
There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems.
In the $k$-Path problem where we are looking for a simple path of ...
- 1,700
25
votes
Accepted
How "hard" is it to maximize a polynomial function subject to linear constraints?
Your problem is NP-hard, even for polynomials of degree 2.
The crucial reference is
Theodore Motzkin and Ernst Strauss (1965)
"Maxima for graphs and a new proof of a theorem of Turan"
...
- 5,772
24
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, ...
- 20.8k
24
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
Gustav Nordh commented on by Theorem 5 (page 29). Specifically, the function
$$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$
computes the function which is $1$ only if $x$ and $y$ are ...
- 349
22
votes
Accepted
Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?
It is true that if the function $f$ is given by an oracle, then a randomized algorithm is exponentially faster than any deterministic algorithm. With an oracle function, however, this is not a $BPP$ ...
- 11.3k
20
votes
Accepted
Intersection of languages in NP
Just an extended comment to better explain ARi's comment (I was writing it while I saw it).
It is sufficient to use a "large gap" approach similar to the one used in Lardner's theorem; for example:
$...
- 22.6k
20
votes
Tardos Function Counterexample to Blum's $P\neq NP$ Claim
so these remarks imply that the Tardos function $f$ is the same as
CLIQUE.
Short answer - NO.
It is only a *monotone* "clique-like": accepts all $k$-cliques, and rejects all complete $(k-1)$-...
- 6,685
17
votes
Accepted
Potentially equal complexity classes without known contradictory relativizations
I think the biggest such example at present is $BQP $ (quantum polybomial time) vs $PH $ (the polynomial time hierarchy). Significant effort has been put into separating them relative to an oracle, ...
- 27.3k
17
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
Could one use list decoding of Reed-Solomon codes to show Andreev's POLY function is in P, similar to the way Sivakumar did in his membership comparable paper? Or is the POLY function known to be NP-...
- 8,616
16
votes
Accepted
Natural candidates for NP-E and E-NP
TQBF (True Quantified Boolean Formulas) is in E and won't be in NP unless NP = PSPACE.
A language in NP-E is trickier. Such a language would also be in NP-NTIME(n) and we don't have great examples of ...
- 8,616
15
votes
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
He has updated his arXiv to say his proof is incorrect:
The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my ...
- 421
14
votes
What are the relationships between those hypotheses in Fine-Grained Complexity Theory?
This is a recent paper introducing Nondeterministic Strong Exponential Time Hypothesis (NSETH), which is an extension of SETH.
NSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT ...
- 141
13
votes
Problems in NC not known to lie in NC2
Disclaimer: I'm not an expert in fast parallel algorithms, hence the probability that I missed more recent results that put the problems I mention in lower levels of the $\mathsf{NC}$ hierarchy is non-...
- 818
13
votes
Accepted
Power of randomness vs. power of indefinite computation
Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects ...
- 14.3k
13
votes
Accepted
What are the consequences of solving XOR 3-SAT in Logspace?
Take a look at https://www.sciencedirect.com/science/article/pii/S0022000008001141 "The complexity of satisfiability problems: Refining Schaefer's theorem" by Allender et al. which answer your ...
- 1,047
13
votes
Accepted
Structural Complexity Theory References
I don't think there really are canonical references for this stuff (roughly: advanced modern structural complexity theory), but here are some references. This list is partially geared towards my ...
- 36.9k
12
votes
Accepted
Example of something that’s different for generic and random oracles?
P = UP with a generic (assuming P = PSPACE) but they are separate relative to a random oracle.
In the other direction P = Promise-BPP relative to a random but separate relative to a generic. Can't ...
- 8,616
12
votes
$BPL$ with polylog random bits is in $L$
It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be ...
- 5,350
11
votes
Problems with big open complexity gaps
The Skolem problem (given a linear recurrence with integer base cases and integer coefficients, does it ever reach the value 0) is known to be NP-hard and not known to be decidable. As far as I know ...
- 50.9k
11
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
Computing VC dimension seems unlikely to be in polynomial time, but has a quasipolynomial time algorithm.
Also, it seems hard to detect a planted clique of size $O(\log n)$ in a random graph, but ...
- 2,295
11
votes
Uncertainties in GCT program
It depends what you count as "the GCT program."
Consider the specific suggestion (GCT I, GCT II) to use the vanishing/nonvanishing of certain multiplicities in the orbit closures of the determinant ...
- 36.9k
11
votes
Accepted
Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?
First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below).
We want ...
- 2,758
11
votes
Accepted
On sparse complete sets and P vs L
Yes, exactly what you suggested is true: if there is a sparse $\mathbf{P}$-complete set under log-space many-one reductions, then $\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 ...
- 1,733
Only top scored, non community-wiki answers of a minimum length are eligible