My survey article on P vs. NP (2017)
scottaaronson.com
scottaaronson.com
Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. However, if all answers can be found easily as well as checked, if only we knew how, then P equals NP. The area has intrigued mathematicians and computer scientists since Alan Turing, in 1936, found that it's impossible to decide in general whether an algorithm will run forever on some problems. Resting on P versus NP is the security of all online transactions which are currently encrypted: if it transpires that P=NP, if answers could be found as easily as checked, computers could crack passwords in moments.
With
Colva Roney-Dougal Reader in Pure Mathematics at the University of St Andrews
Timothy Gowers Royal Society Research Professor in Mathematics at the University of Cambridge
And
Leslie Ann Goldberg Professor of Computer Science and Fellow of St Edmund Hall, University of Oxford
And every week, Bragg intelligently moderates the conversation -- not as an expert, but as somebody who sounds like he's better informed than just feeding them the outlines they write for him.
But the techniques used would likely be insightful. Particularly with proving cryptographic protocols beyond "we had a contest & damn are these bits ever uncorrelated"
Or obviously even if the proof does show you how to do it but the exponent is some insanely large number (see some of Scott Aaronson's other articles about "busy beaver numbers"), then that does not change anything practically either.
Also, finding such algorithms should significantly expand our capabilities by expanding our understanding.
Let me give an example where such a case exists. In 2005, a paper came out finding an algorithm for determining undirected graph connectivity in log space, which means you can't keep an unbounded stack of nodes that you have visited (as the trivial depth-first or breadth-first search algorithms do). This algorithm relies on converting the input graph using an "expander graph," basically replacing every node with an instance of a graph. When I computed how large an expander graph had to be, I found that the smallest one was ... 3^65536. It's still a constant factor, but it's larger than the number of atoms in the universe. This kind of constant factor isn't unusual for combinatorics problems (this is the same kind of space where Graham's number comes up).
My suspicion is that if P=NP, it's likely to be so only via this kind of crazy combinatorial input, which is to say, the P algorithm is completely impractical.
Outside of combinatorial algorithms, there are several other cases where the asymptotically faster algorithms are generally disfavored due to practical concerns: primality testing (AKP is a P algorithm, but slower in practice); matrix multiplication (we keep finding better exponents, but the dominant algorithm remains Strassen, and even then, that's only going to be used for distributed matrix multiplication). You mention linear programming, but my understanding is that interior point methods are generally preferred in modern implementations over simplex methods, the former being polynomial and the latter exponential (although very often polynomial in practice--another great example of typical case being far faster than worst case).
A proof of P!=NP would tell us two things. First, that there's something inherently different about NP-complete problems, and the proof would tell us exactly what.
Second, it would tell us how to figure that out, inevitably with an entirely new toolset for classifying problems. It would reverberate all over the computational complexity space and probably even give us new ideas for number theory.
The way I see it NP problems require exponential time by default. The reason some of them can be solved in polynomial time is because those problems contain some special structure that allows you to short-circuit the general solution with some kind of "trick".
Then P vs. NP boils down to does there exist a "general trick". In other words do all NP problems contain structure that can be exploited to short-circuit the calculation or not.
I do agree that actually proving that P != NP seems like it would require discovering some as yet unknown structure behind virtually all of mathematics, simply because the hypothetical "general trick" could be hidden in just about any mathematical structure we know about (or even in one we haven't discovered yet).
And we can strengthen this statement a bit, to really hammer home the intuition of why P=NP would be such a radical discovery.
"Simulating an arbitrary non-deterministic Turing machine for K steps" is itself an NP-complete problem, which would be solvable by a polynomial algorithm if P=NP. In other words, it's not just that all NP problems would have some structure that a sufficiently clever programmer could exploit; it's that there would exist a single algorithm that could automatically discover and exploit such structure in any NP problem.
To which he replies,
>>to make a sweeping statement like P ̸= NP, about what polynomial-time algorithms can't do, will require an unprecedented understanding of what they can do. This will almost certainly entail the discovery of many new polynomial-time algorithms, some of which could have practical relevance. In Section 6, we’ll see much more subtle examples of the “duality” between algorithms and impossibility proofs, with progress on each informing the other.
That's what we have, but it's not really comforting.
Now if you think what it'd mean to proove that e.g. a public key crypto system is secure, it almost implies that you'd need to proove p!=np before that. I.e. prooving p!=np would not proove that cryptography is secure, but it may be the first step and the understanding gained from prooving p!=np may mean that there's a much better understanding of complexity in general, which will help.
https://cs.stackexchange.com/questions/6650/how-can-p-np-enh...
It can be reduced already, but then 3-sat can be solved in P time
For example, you can assume part of the plaintext (like a header in transmission) and solve an equation (which can be restated as a SAT instance) that yields you a key assuming certain cryptographic algorithm was used. So pretty much all cryptography relies on P!=NP.
But don't worry, if that happens the world would be so different there might no longer be a need for cryptography.
https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
https://en.wikipedia.org/wiki/NP-intermediate
Under the assumption that we understand P and NP a heck of a lot more if we were able to proof their distinctness, this hierarchy could possibly be used for actually USEFUL proof of work in crypto currencies, by choosing problems with exactly the right difficulty from a problem domain like protein folding.
Archive: http://web.archive.org/web/20210323141221/https://www.scotta... Archive of the pdf in question: http://web.archive.org/web/20210313130122/https://www.scotta...
You can also find the minimum element of a list in logarithmic time instead of linear time if you have enough parallelism available, even though finding the minimum element is O(N).
By that definition computers have AI because humans can communicate through them (i.e. connect a prism to do O(1) Furrier transform vs connect a human for computer to behave like human).
Also, analog computation schemes tend to rapidly encounter fundamental physical limits. If calculating an N-bit result requires a measurement with N bits of precision, then adding one additional bit tends to require twice as much energy, or twice as big an apparatus, or something of the sort. So even if the "computation" itself looks as if it's O(1), your resource consumption is still exponential.
But the sentiment is not wrong. There are potentially new computing paradigms that are really good for things that our machines are really bad at. I've always been fascinated by analog computers (machines, really). The old firing solution computers for torpedoes are just precisely machined wheels and gears (TDC, it's called).
But ultimately, for information exchange and transmission, it does seem nature selected for something that strangely appears to be Turing-like: DNA. Perhaps there's something to this Turing machine model after all? I find it interesting too, is all I'm saying.
Only because the prism puts an upper bound on the size of the input. If you do that, every problem is O(1).
That's technically true, but it misses the point rather badly. The size of the problem that a prism can accept as input is constrained by the physical size of the prism. The size of the problem that a computer can accept as input is constrained only by time. So yes, technically, the universe will eventually undergo heat death and so the amount of time available is finite, but that's just not very interesting.
To be fair, this is only an unproven hypothesis. The Church-Turing Thesis is an assumption about the physical world (which so far seems to have held up pretty well) rather than a theorem.
Yes, it is. Turing machines can do math, so a system that exhibited behavior that could not be emulated by a TM would have to be one whose behavior is not describable mathematically. No one has been able to come up with any idea of what such a system would even look like, let alone actually produce an example.
> Wrong theories have been around for much longer.
And crackpots have been around for even longer.
> And crackpots have been around for even longer.
There’s nothing crackpoty about what I’m saying.
Turing machines are polynomially worse than von Neumann machines. It'd be hard to factor 16-bit numbers on a physically realizable Turing machine, while we can do hundreds of bits on our laptops.
No, they are not.
> It'd be hard to factor 16-bit numbers on a physically realizable Turing machine, while we can do hundreds of bits on our laptops.
Here you have done exactly what a prism does: put an upper bound on the problem size. When you do that, you can just precompute all the possible answers (because there are only a finite number of possible inputs) and the computation becomes O(1).
To assess computational complexity you have to do it with respect to an unbounded input size. And when you do that, you will find than VNMs have only a constant advantage over TMs, not a polynomial one. This is because a VNM has a finite word size and so can only randomly address a finite memory, and so it can be emulated by a TM in constant time.
There is no getting around this. Either you bound the input size or you don't. If you do, it's all O(1) which isn't very interesting. If you don't, all computational models are equivalent (except quantum computers, which give you an exponential speedup for some problems). This is the entire reason that computational complexity theory is interesting in the first place, because you can talk about it coherently without committing to a particular model of computation.
I suspect there are none, because you need at least n bits of state in order for a program to run for 2^n cycles before halting.
In other words NP ⊆ PSPACE and the polynomial growth in space is always at least degree 1 for any algorithm that is more than O(n).
So I don't think it's true that "the size of the problem that a computer can accept as input is constrained only by time", except for some O(1) algorithms like computing the parity of a bit stream. Which isn't the sort of thing people are building optical computers to solve.
Only for a non-embedded system. Prisms are embedded: you have to illuminate them to get them to do anything interesting. So to compare apples and apples you have to consider a case like: connect a microphone to your computer and compute the SHA512 hash of the audio stream. That will require only O(1) space but will never halt as long as the microphone is plugged in.