2 ms·
Integer factorization is not known to be NP-complete, so as far as we know, finding an efficient way to factor integers would not tell us anything about P vs. N
by teraflop 6y ago
Integer factorization is not known to be NP-complete, so as far as we know, finding an efficient way to factor integers would not tell us anything about P vs. NP.
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.