holds, like a Sudoku puzzle having a solution. Every NP search problem has a
zero-knowledge proof under the appropriate hardness assumptions.
Online poker is generally played
through some “trusted” Web site, usually somewhere in the Caribbean. Can
we play poker over the Internet without
a trusted server? Using the right cryptographic assumptions, not only poker
but any protocol that uses a trusted party can be replaced by one that uses no
trusted party and the players can’t cheat
or learn anything new beyond what they
could do with the trusted party.b
Eliminating Randomness. In the 1970s
we saw a new type of algorithm, one that
used random bits to aid in finding a solution to a problem. Most notably we
had probabilistic algorithms35 for determining whether a number is prime, an
important routine needed for modern
cryptography. In 2004, we discovered
we don’t need randomness at all to efficiently determine if a number is prime. 2
Does randomness help us at all in finding solutions to NP problems?
Truly independent and uniform
random bits are either very difficult or
impossible to produce (depending on
your beliefs about quantum mechanics). Computer algorithms instead use
pseudorandom generators to generate a sequence of bits from some given
seed. The generators typically found on
our computers usually work well but occasionally give incorrect results both in
theory and in practice.
We can create theoretically better
pseudorandom generators in two different ways, one based on the strong
hardness assumptions of cryptography
and the other based on worst-case complexity assumptions. I will focus on this
We need to assume a bit more than
P ≠ NP, roughly that NP-complete problems cannot be solved by smaller than
expected AND-OR-NOT circuits. A long
series of papers showed that, under this
assumption, any problem with an efficient probabilistic algorithm also has
an efficient algorithm that uses a pseudorandom generator with a very short
seed, a surprising connection between
hard languages and pseudo-random-ness (see Impagliazzo23). The seed is so
short we can try all possible seeds effi-
b See the survey of Goldreich18 for details.
ciently and avoid the need for randomness altogether.
Thus complexity theorists generally
believe having randomness does not
help in solving NP search problems and
that NP-complete problems do not have
efficient solutions, either with or without using truly random bits.
While randomness doesn’t seem
necessary for solving search problems,
the unpredictability of random bits
plays a critical role in cryptography and
interactive proof systems and likely cannot be avoided in these scenarios.
could Quantum computers
Solve NP-complete Problems?
While we have randomized and non-randomized efficient algorithms for determining whether a number is prime,
these algorithms usually don’t give us
the factors of a composite number.
Much of modern cryptography relies on
the fact that factoring or similar problems do not have efficient algorithms.
In the mid-1990s, Peter Shor34
showed how to factor numbers using
a hypothetical quantum computer. He
also developed a similar quantum algorithm to solve the discrete logarithm
problem. The hardness of discrete logarithm on classical computers is also
used as a basis for many cryptographic
protocols. Nevertheless, we don’t expect that factoring or finding discrete
logarithms are NP-complete. While we
don’t think we have efficient algorithms
to solve factoring or discrete logarithm,
we also don’t believe we can reduce NP-
complete problems like Clique to the
factoring or discrete logarithm problems.
So could quantum computers one
day solve NP-complete problems? Unlikely.
I’m not a physicist so I won’t address
the problem as to whether these machines can actually be built at a large
enough scale to solve factoring problems larger than we can with current
technology (about 200 digits). After billions of dollars of funding of quantum
computing research we still have a long
way to go.
Even if we could build these machines, Shor’s algorithm relies heavily on
the algebraic structures of numbers that
we don’t see in the known NP-complete
problems. We know that his algorithm
cannot be applied to generic “black-box”
NP can be seen as a graph where every
element is connected to every other
element. over these pages a deconstruction
of the graph is shown.
search problems so any algorithm would
have to use some special structure of NP-
complete problems that we don’t know
about. We have used some algebraic
structure of NP-complete problems for
interactive and zero-knowledge proofs
but quantum algorithms would seem to
require much more.
Lov Grover19 did find a quantum algorithm that works on general NP
problems but that algorithm only achieves
a quadratic speed-up and we have evidence that those techniques will not go
Meanwhile quantum cryptography,
using quantum mechanics to achieve
some cryptographic protocols without
hardness assumptions, has had some
success both in theory and in practice.
a New hope?
Ketan Mulmuley and Milind Sohoni
have presented an approach to the P
versus NP problem through algebraic
geometry, dubbed Geometric Complexity Theory, or GCT. 29
This approach seems to avoid the dif-