17
Gerhard Woeginger has an up-to-date page with all attempts to (dis)prove the P vs NP question:
https://www.win.tue.nl/~gwoegi/P-versus-NP.htm
8
Sorry for the very "big picture" answer from a non-quantum-theorist, but this contrast might help: you could describe algorithms as the study of how to solve computational problems, whereas complexity theory studies the resources (especially time) required in theory to solve them. How hard are these problems really at some fundamental level, and how are they ...
6
I think the big question here is "What does the complexity/power of algorithms look like in our universe?" If we ignore relativity and QM, then plain vanilla Turing machines are a decent model. But relativity and QM are our current best physical theories for explaining the universe, so the question is whether taking relativistic or quantum effects changes ...
4
The last such serious attempt was likely Norbert Blum's attempted proof of P $\neq$ NP in 2017. Not long after it was submitted to arxiv, it was discovered to have a serious (but nontrivial) flaw.
This proof was discussed on stackexchange here (and in more detail here), and on several blogs (like Godel's Lost Letter).
4
One obvious answer is "spaghetti sort", or in other words - sorting in a spaghetti model.
Intuitively, the spaghetti model says that your integers are given as lengths of (uncooked) spaghetti, and you sort them by placing them on a table, and then lowering your hand until you hit the tallest spaghetto (for spaghetto is the singular of spaghetti). You take ...
2
If one considers geodesics as a worldline geometric analysis of Grover search, show under a metric that Grover search follows a geodesic. Under small perturbations too, Grover search works well. Also, given a perturbation, under a type of kahler metric - the Fubini-Study metric - Grover search cannot follow a geodesic, see for perturbation study. ...
2
I think you could be interested by the counting class Span-P (which is the class of counting problems that can be defined as the number of distinct outputs of a nondeterministic Turing machine running in polynomial time). It was introduced in this paper. Both 1) and 2) are in Span-P. For 1): guess a subgraph, then guess a Hamiltonian circuit, then output the ...
2
Our FOCS'17 paper on the Short Presburger Arithmetic is an example of a "natural" problem which is NP-c, and uses a constant number $C$ of integers in the input, say $C< 220$. It is different from Manders-Adleman in that the constraints are all inequalities. See Gil Kalai's blog post for some background.
2
Some heuristic evidence: to the best of our knowledge $\pi(n)$ looks like a simple function corrected by random fluctuations. Thus I’d expect a poly-time machine with a $\pi(n)$ oracle to be no stronger than such a machine with a random oracle, and w.r.t. a random oracle $X$ adding a separate random oracle $Y$ to $\mathsf{P}$ gives $\#\mathsf{P}^X \not\...
1
That's a nice list! Unfortunately, I think the function $n\left(\log(n)^{\log\log(n)}\right)$ is not in your list. Yet it grows faster than $n\log(n)$ and slower than $n^{1+\varepsilon}$. Similarly, the function $n\left(\log\log(n)^{\log\log\log(n)}\right)$ is not in there, yet it grows faster than $n\log\log(n)$ but slower than $n\log(n)^{\varepsilon}$.
...
1
One thing to note is that there are a lot of practical situations where we can get better than $O(n \log n)$ sorting. I'm not sure where the best reference is, but this library has a link to a video talk by Fritz Henglein, who is who I've heard originated the technique (unfortunately the links to his actual papers are broken).
The idea is to extend radix ...
Only top voted, non community-wiki answers of a minimum length are eligible
