How to solve NP-problem using hydrodynamics of electrons

[Duda Jarek]

Let's take some NP-problem: we have a verifier which can quickly say that given input is correct or not, but there is huge number of possible inputs and we want to tell if there is a correct one (find it).

Such problem can be for example finding a divisor (RSA breaking) or finding a key that if we use it to decrypt the beginning of the file, there will be significant correlations (brute force attack).

 

Imagine we have a chip with 'input' and 'output' in which is implemented (e.g. FPGA):

 

IF 'input' verifies the problem

- THEN send 'input' to 'output'

- ELSE send next possible 'input' (cyclically) to 'output'

 

such that this chip uses only basic logic gates - computations are made in some small number of layers - IT DOESN'T USE CLOCK (we can do it for some NP problems like 3SAT).

 

Now connect it's 'output' and 'input' to make a loop.

 

Such loop will be stable if it has found a solution (which can be transferred out).

If there would be a clock, in each cycle there would be checked one input.

If not, it's no longer classical computer: while removing the clock/synchronization we are destroying the order and releasing all it's statistical, quantum properties to make what physics do the best: solve its partial differential equations. Now it became continuous and so it can go with energy gradient to some local minimum, but the only local minimals are stable states (solutions). Every other is extremely unstable - electron fluid won't rest until it find a solution. The statistics, differences between propagation times will create extremely fast chaotic search for it.

I'm not sure, but it could find solution qualitatively faster than classical computer.

 

I know - there can be a problem with nonlinearity of transistors? If yes, there are plenty of technologies, maybe some of them would handle with it?

 

This loop computer idea is practically simplified from time-loop computer idea:

http://www.scienceforums.net/forum/showthread.php?p=453782

Edited December 22, 2008 by Duda Jarek
multiple post merged

[Harlequinne]

the straightest line between two random points or a grouping OF groups in an INFINTITE

domain,in my mind renders the problem immediately unquantifiable. The straightest line is sometimes the quickest way but not always,particularly given all possibilities.

Remeber that the fastest route has to be found via algorithm.I find common sense to be more efficient.in the usa with cities away from the centre makes a good map of problem at hand.Given all cities must be visited,the computation is impossible or is it? This is the question ,yes? my question was a)the route-finding or every possible permutation of every journey is sequential and systematic,like odds in Poker,at least the research.

b)the mileometer then clocks it up,using plus.IF an efficient path is found and an alternative route discovered what if a minus sign comes into use? Does that differentiate between N¬NP? Also contrast between choices...how is ¬NP defined?

the manipulation of operations could make it be seen incompatible.

Also,where is the equals sign? when do they equate?

[Duda Jarek]

In this approach instead of trying to solve problem classically, we change it into continuous problem and use physics natural ability to solve some partial differential equations.

Thanks of it could take some short path to find the solution.

 

I was pointed out that the problem is that gates looses it's properties in high frequencies, but it can be a matter of choosing proper technology.

http://groups.google.com/group/sci.crypt/browse_thread/thread/736fd9f3e62132c2#