Hot answers tagged

58

Strassen's statement needs to be put into context. This was an address to an audience of mathematicians in 1986, a time when many mathematicians did not have a high opinion of theoretical computer science. The complete statement is For some of you it may seem that the theories discussed here rest on weak foundations. They do not. The evidence in favor of ...


21

I can see three related ways to understand the question: 1) Can we we regard $NP \ne P$ as a fundamental principle of computational complexity theory, even before we can prove it? 2) Does the $NP \ne P$ principle extends beyond its narrow mathematical meaning? 3) Does the $NP \ne P$ principle can be regarded as a physical law. I think that there are ...


17

You seem to have the idea that a quantum gate is a physical thing rather than just a conceptual thing. It doesn't necessarily work that way. While CMOS gates are usually actual physical devices, quantum gates may be just conceptual. Consider an ion trap. The ions represent qubits by using one electronic state as a $|0\rangle$ and another as a $|1 \rangle$...


16

P and BQP are decision-problem classes, i.e. the correct output is always a deterministic functions of the inputs. The only question is whether randomness helps "along the way" to speed up computing this deterministic function (at the cost of sometimes being wrong), or does not. This is the key point: P=BQP says nothing about outputting random strings in ...


14

Using nested dissections you can even solve a linear system (based on a planar graph) in $O(\sqrt{n^\omega})$. This was for example noted in a paper I have with Günter Rote and Ares Ribó and in this paper by Alon and Yuster. The former paper also contains an approach how to compute the pairwise resistances between vertices on a a common face in $O(\sqrt{n^...


13

I'm not sure I understand. A physical law (of the kind you indicate) is a mathematical expression of a model (in that example, relativity) that claims to capture reality. A physical law can be proved wrong if the underlying mathematics is incorrect, but it can also be wrong if the underlying model changes (for example, newtonian mechanics). P vs NP is a ...


12

The general belief seems to be that the expansion in $\alpha$ is an asymptotic series but not a convergent series. The handwaving estimate is that in $\sum_k c_k \alpha^k$, the scaling for the coefficients is roughly $c_k \sim k!$. So, since $\alpha \simeq 1/137$ the terms will start to get bigger rather than smaller for $k$ larger than around 137. (I assume ...


11

The questions touches on some very interesting issues regarding quantum computation (and randomness). BQP is the class of decision problems that can be solved efficiently (in polynomial time) but it is not clear that referring just to decision problems suffices to do justice to the power of quantum computing. If we let QSAMPLING describes the probability ...


10

If quantum computers can simulate in polynomial time the Standard Model, which is a quite complicated quantum field theory, then probably the Standard Model does not provide any extra computational power beyond BQP. Simulating quantum field theories with a quantum computer is not an easy task, but a start has been made by this paper by Jordan, Lee, and ...


9

I'm not 100% sure what the question is about, but the title seems to ask about computation that allows failure. There is a lot of work on noisy (erroneous) computation in the sense that I think you are asking about. I don't have time to give a complete overview, but here are some pointers that may be of interest. Distributed systems. This is probably by far ...


9

I extend my comment in an answer. By rewriting $e^{i \cdot sgn(\mu)\theta} = \cos(sgn(\mu)\theta)+i\sin(sgn(\mu)\theta) = \cos(\theta)+i \cdot sgn(\mu)\sin(\theta)$ we have: $Det_\theta(A) = \cos(\theta)Perm(A)+i\sin(\theta)Det(A)$. Thus, if $\cos(\theta) \neq 0$, we have $Perm(A) = (Det_\theta(A)-i\sin(\theta)Det(A))/\cos(\theta)$, meaning that $Det_\...


9

Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. Because of this these problems can often be NP-hard but not (or not obviously) NP-complete. For instance, we do not know whether the Euclidean TSP (for integer ...


9

You appear to be positing a universe where (a) the fine-structure constant has an exact value and (b) we can measure as many digits of it as we want. Thus, if a Turing machine cannot compute the exact value of the fine-structure constant, it cannot predict the outcome of an arbitrary experiment. I don't believe (b) is the case. Generally, the way that ...


8

To answer your original question: Yes at least Scott Aaronson believes that $P \ne NP$ is a law of nature. He proposed the following formulation "The NP Hardness Assumption : There is no physical means to solve NP complete problems in polynomial time". He gave a nice talk at the University of Waterloo titled Computational Intractability As A Law of ...


8

He didn't have any major impact on computer science. His writing in computer science are limited to popsci and more recently raising public concerns about AI.


8

There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See Farhi et al's paper Quantum Money from Knots, Mark Zhandry's paper Quantum Lightning Never Strikes the Same State Twice, Daniel Kane's paper Quantum Money from Modular Forms. In order to make ...


7

Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as: circuit-based quantum computing (CBQC) Adleman-Lipton model (a model for computing using DNA) Turing machine model (a model where computations are done with symbols on a tape) One can devise algorithms using ...


7

The Black Hole Information Paradox seems relevant to me, as it concerns information theory, which can be seen as close to computer science. To sum up, the paradox in question is that when objects or in general waves carrying information are swallowed by a black hole, the information they carry seems to be destroyed. This violates principles in quantum ...


7

Yes, if you somehow had a scheme that allows to compute/measure more and more digits of the fine-structure constant $\alpha$ then $\alpha$ should be Turing computable according to the Church-Turing thesis. But in practice, $\alpha$ is based on some measured quantities, we have no Theory of Everything (TOE) for physics, and it is not clear that $\alpha$ is a ...


6

Basically everything that is known about the Quantum PCP conjecture has been collected in this survey by Dorit Aharonov, Itai Arad, and Thomas Vidick: The Quantum PCP Conjecture See also Thomas' blog post on the topic.


6

We will never be able to prove this statement, because we can never be able to know for sure whether we have the exact laws of physics, or just a very good approximation to them. Even if we had a satisfactory theory of everything which we could use to make good predictions about every experimentally measurable physical system, there would be no way to tell ...


6

Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time. But in context the author is in the middle of explaining the complexity class BQP (bounded-probability quantum polynomial-time). I think they're just making sure that you ...


6

With thermodynamics you have to be careful with the kind of reductions you allow, or (as Peter Shor pointed out) there can be essentially no thermodynamic relationship implied by a reduction. For example, if we consider not just the complexity of languages, but also the complexity of functions, every language is equivalent (under pretty simple reductions) to ...


5

A quantum Fourier transform is a unitary operation, so the number of basis states of the input and output must be the same. The number of basis states before the Fourier transform is 120, the number of group elements. The number of basis states after the Fourier transform is 120, in this case broken up according to the identity $$ 120=1^2+1^2+4^2+4^2+5^2+...


5

First of all is the known weaker result $NL\neq PSPACE$ or the stronger conjecture $NP\neq coNP$ possible laws of nature? Then we can ask questions about if $P\neq NP$ is a law of nature.


5

Everything interesting happens in this paper happens within the 2D subspace generated by the two vectors $|s\rangle$ and $|w\rangle$. The vector $|r\rangle$ is a vector from this subspace orthogonal to $|w\rangle$, giving us the basis $|w\rangle, |r\rangle$, where the analysis will be very simple (using 2x2 matrices). The norm in the second question is ...


5

[The following is more an extended comment with pointers than a real answer.] If you were in France, a good answer would be combinatorial physics. I say "if you were in France" because, for reasons that escape me but that must be mostly historical, in France combinatorics is considered part of theoretical computer science :-) In the rest of the world, ...


5

Not a direct answer but something : He is mentioned 19 times in these lecture notes of Scott Aaronson, https://www.scottaaronson.com/barbados-2016.pdf That says something, I guess? :D


4

For the consequences of such transmission to theoretical computer science (the only aspect of your question that is on-topic here) see Aaronson and Watrous's "Closed Timelike Curves Make Quantum and Classical Computing Equivalent".


4

Takens himself did some CS work although not TCS work. He did some attractor reconstruction stuff with neural networks, for example (https://clgiles.ist.psu.edu/papers/NC-2000-learning-chaos-nn.pdf) and it does use his embedding theorem to suggest nonlinear autoregressive (time delay) neural nets, and look towards actual recurrent networks. Overall, ...


Only top voted, non community-wiki answers of a minimum length are eligible