3
$\begingroup$

In NP problems we can cheaply (polynomial time) test if a given input is satisfying, but the difficulty is that there is an exponential number of possible inputs - the question is if e.g. there is a satisfying input.

Imagine there is a simple hardware implementation of verifier (e.g. in form of 3-SAT problem): as a few layers of logic gates, returns 1 if the input is satisfying, 0 otherwise.

Now build a circuit which returns "input+1" (cyclically) for non-satifying inputs, and "input" for a satisfying one ... and connect its output to input:

enter image description here

So the original NP problem has became finding a fixed-point of such loop. If this electronic circuit has a clock (is synchronized), it would test one input per step, until reaching a fixed point - a solution.

But what if there is no clock/synchronization? Just hydrodynamics of electrons flowing around the circuit, trying to stabilize the flow to minimize fluctuations. Like NOT gate connected into a loop should create oscillation (I think it strongly depends on technology of gates?).

Could such unsynchronized continuous circuit be faster - use some shortcuts while finding fixed point of the loop: solution of our problem?

While we know that with clock it stabilizes in exponential time, without the clock there are basically 3 options:

  1. Without clock it will no longer stabilize,
  2. It will stabilize in comparable time,
  3. It will stabilize essentially faster (using some shortcuts in the search).

Which is the proper possibility? Can we say anything certain without experiment (ASIC?) - are there some arguments pro or against any of these possibilities?

$\endgroup$

closed as off-topic by sammy gerbil, Norbert Schuch, knzhou, Kyle Kanos, Jon Custer Oct 28 '17 at 15:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "We deal with mainstream physics here. Questions about the general correctness of unpublished personal theories are off topic, although specific questions evaluating new theories in the context of established science are usually allowed. For more information, see Is non mainstream physics appropriate for this site?." – Norbert Schuch, knzhou, Kyle Kanos, Jon Custer
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Could anybody explained why it is "on hold"? This is just a question about behavior of electronic circuit - a few layers of logic gates, connected in a loop, without clock to synchronize its behavior - why it was classified as "off -topic" or not belonging to mainstream physics? I can modify it, but first I need to understand what is the issue? $\endgroup$ – Jarek Duda Oct 29 '17 at 14:38
  • 1
    $\begingroup$ So you're asking: can I remove the clock from a circuit and run it, and then maybe some magic happens, and I can solve NP-complete problems faster than conventional circuits? This question probably should have been closed as too vague – you're not really being very clear about the "magic" part – and not as non-mainstream physics (unless you take the "magic" literally). $\endgroup$ – Peter Shor Oct 30 '17 at 11:55
  • 1
    $\begingroup$ Great, maybe you could suggest some interesting literature on non-standard physical approaches to NP? What should I look for? Converting NP-complete problem into a physical system is not an easy task, the above "loop computer" is kind of direct way so might be considered earlier, but I couldn't find any information in literature when I was looking in 2008 (?) $\endgroup$ – Jarek Duda Oct 30 '17 at 20:43
  • 1
    $\begingroup$ Scott Aaronson NP-Complete Problems and Physical Reality. Vergis, Steiglitz, Dickinson, The Complexity of Analog Computation. And you should be able to find more by looking at their bibliographies and the papers that cite them. $\endgroup$ – Peter Shor Oct 31 '17 at 0:21
  • 1
    $\begingroup$ There's a fourth possibility: it stabilizes at some state that gives no information about the desired solution. $\endgroup$ – Peter Shor Oct 31 '17 at 15:19