Research ArticleCOMPUTER SCIENCE

Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states

See allHide authors and affiliations

Science Advances  03 Jul 2015:
Vol. 1, no. 6, e1500031
DOI: 10.1126/sciadv.1500031
  • Fig. 1 Scheme of the memcomputing architecture used in this work to solve the subset sum problem.

    The central spectrum was obtained by the discrete Fourier transform of the experimental output of a network of six memprocessors encoding the set G = {130, −130, −146, −166, −44, 118} with fundamental frequency f0 = 100 Hz.

  • Fig. 2 Schematic of the modules.

    (A) Simplified schematic of the memprocessor architecture used in this work to solve the SSP (more details can be found in Materials and Methods). (B) Schematic of the frequency shift module.

  • Fig. 3 Spectra of the internal collective state of three different networks with fundamental frequency f0 = 100 Hz.

    The four-memprocessor network encodes the set G = {130, −130, −146, −166}. The five-memprocessor network encodes G = {130, −130, −146, −166, −44}. The six-memprocessor network encodes G = {130, −130, −146, −166, −44, 118}.

  • Table 1 Measurements from the readout unit of Fig. 1 for a six-memprocessor network with fundamental frequency f0 = 100 Hz encoding the set G = {130, −130, −146, −166, −44, 118}.

    In the fifth and sixth columns, the voltages are respectively given by Embedded Image and Embedded Image. The last two columns are the analytical results.

    |S|ωs/(2π)
    (kHz)
    Embedded Image
    (mV)
    Embedded Image
    (mV)
    Vs
    (V)
    V-s
    (V)
    No. of
    subset
    sum s
    No. of
    subset
    −s
    0031.701.021.0211
    747.415.315.01.940.0220
    13013.0−0.214.90.94−0.9711
    14614.614.815.8−0.061.9602
    24824.87.67.20.950.0210
    48548.5−0.4−0.7−0.070.0200
    48648.6−8.96.6−0.140.9901

Supplementary Materials

  • Supplementary Materials

    This PDF file includes:

    • Fig. S1. Memprocessor module.
    • Fig. S2. Schematic and picture of the test bench for the laboratory experiment.
    • Fig. S3. Pictures of the laboratory test bench.

    Download PDF

    Files in this Data Supplement:

Navigate This Article