New answers tagged cc.complexity-theory
-2
Everyone trying to get you to fix their computer.
Or install an app.
Or sign in with two-factor auth.
Or fix the projector.
0
The implication that PH collapses to BPP, and is therefore effectively tractable, is very distressing, but fortunately appears to be based on a confusion of randomized complexity classes. Zachos names a class R for which a supermajority of paths of a NP machine accept if the input is a member of the language, and all paths reject if not. The class RP in ...
4
A simple answer is that we're "pretty sure" that $\mathsf{P} \neq \mathsf{NP}$, and we're "pretty sure" that $\mathsf{P} = \mathsf{RP}$, so we're "pretty sure" that $\mathsf{NP} \neq \mathsf{RP}$".
15
$\mathsf{P}/\mathsf{poly}$ is the set of decision problems solvable by polynomial-size circuits. We know $\mathsf{RP} \subseteq \mathsf{BPP}$ and, by Adleman's theorem, $\mathsf{BPP} \subseteq \mathsf{P}/\mathsf{poly}$. So among the only mildly shocking implications of $\mathsf{RP}=\mathsf{NP}$ would be $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$.
...
13
This answer is not about correctness of the paper on which the author might have known something already in $2014$ since Item $218.$ in https://personal.utdallas.edu/~farago/publ08.pdf indicates a document with almost the same title. It is surprising he waited for six years. It is also interesting that no one knew anything of this technique. Perhaps my guess ...
0
Here is a link to some lecture notes that answer my question - http://www.cs.cornell.edu/~sabhar/publications/iaspcmi-proofcomplexity00.pdf
Proof complexity is a vast field of mathematics.
4
I believe I can partially answer your question as to why the bounds of $\{-n^3, ..., n^3\}$ are justified.
This paper by Pătraşcu mentions that for 3SUM over any bounded universe of integers of size $u >> n^3$, the universe size can be hashed down to $O(n^3)$ while maintaining the expected $O(n^2)$ run time for 3SUM. Therefore, to prove that 3SUM can ...
4
The following excellent video:
https://www.youtube.com/watch?v=YRiyqc99kd0&t=2661s
and this one:
https://www.youtube.com/watch?v=x-HskkxUuVI&t=1965s
Deals with this issue and Fine Grained Approach to Complexity in general.
9
I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time algorithms (at least via Karp reductions) because it would only improve constants in the exponent of the runtime. In particular, if we reduce 3-SAT to a 3SUM instance of ...
Top 50 recent answers are included
