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,067
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 ...
- 2,039
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,792
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.4k
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,795
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,791
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,791
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
15
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 ...
- 38.5k
14
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-...
- 828
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.5k
13
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,675
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,067
12
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,913
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,791
12
votes
Accepted
Why is the circuit class AC0 unavoidable?
The class $\mathbf{AC}^0$ arises very naturally as the circuit characterization of problems definable by formulas of first-order logic. A language over the alphabet $\{ 0,1 \}$ is in $\mathbf{AC}^0$ ...
- 4,765
12
votes
Accepted
Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$
No. Since universal quantifiers commute with conjunctions, it is easy to see that $\Sigma_2$-SAT with $\psi$ CNF is in NP. If it's really written like this in the book, it's an error.
However, the ...
- 18.6k
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,763
11
votes
"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?
I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = ...
- 8,791
11
votes
Accepted
Does Max Planar 3-SAT admit a PTAS?
Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach.
This has been observed, for instance, in Theorem 17 in
Pierluigi Crescenzi and LucaTrevisan:
"Max NP-...
- 5,792
11
votes
PPAD and Quantum
Two answers that I learnt while writing a blog post about this question
No: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. ...
- 111
11
votes
Accepted
If NP in BPP then NP equals RP
An actual factual reference is
K. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39–43, 1982.
(When I first saw this result --- I ...
- 27.7k
11
votes
Accepted
Complexity class of efficient streaming algorithms
Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it.
Search for "one-way ...
- 27.7k
11
votes
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time $n^{O(\log \log n)}$ [1].
More explicitly, we are given an expression ...
- 903
10
votes
k-Vertex Cover problem is in parameterized Log space
Here is an algorithm that uses $2k^2 + O(\log n)$ space. This is just the observation that the well known "Buss kernel" for Vertex Cover can be computed in log-space:
Say that a vertex has big degree ...
- 3,276
10
votes
Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?
The problem of determining whether a sentence of Presburger arithmetic is true is in between 2-NEXP and 2-EXPSPACE. When the number of quantifier alternations is fixed and at least two, the problem is ...
- 2,592
Only top scored, non community-wiki answers of a minimum length are eligible