  The subset sum problem is a typical NP-complete problem that is hard to solve
efficiently in time due to the intrinsic superpolynomial-scaling property.
Increasing the problem size results in a vast amount of time consuming in
conventionally available computers. Photons possess the unique features of
extremely high propagation speed, weak interaction with environment and low
detectable energy level, therefore can be a promising candidate to meet the
challenge by constructing an a photonic computer computer. However, most of
optical computing schemes, like Fourier transformation, require very high
operation precision and are hard to scale up. Here, we present a chip built-in
photonic computer to efficiently solve the subset sum problem. We successfully
map the problem into a waveguide network in three dimensions by using
femtosecond laser direct writing technique. We show that the photons are able
to sufficiently dissipate into the networks and search all the possible paths
for solutions in parallel. In the case of successive primes the proposed
approach exhibits a dominant superiority in time consumption even compared with
supercomputers. Our results confirm the ability of light to realize a
complicated computational function that is intractable with conventional
computers, and suggest the subset sum problem as a good benchmarking platform
for the race between photonic and conventional computers on the way towards
"photonic supremacy".
