Actually you cannot even run a single instruction during 1ps. Modern CPUs are pipelined and make it look like an instruction takes one cycle. However, between loading of input, processing, and output, ca 20 cycles pass. It's just that with 20 instructions in the pipeline, you might get an effective throughput of 20 instructions per 20 cycles. And this does not even consider cache/memory and i/o access times.

Total I/O latency between signal arriving at PC, and PC answering may well be in the order of many 100 (if not 1000) cycles.

The more general idea behind this is dynamic programming. If you have an equation of N boolean variables, you can brute force in 2^N. If you have M equations of 2^N variables, where equation share variables only with one or more neighbouring equations, you can determine solutions for every equation on its own in M*2^N steps and save those (partial) solutions. Then to find a solution that satifies all equations you just have to find a "path" through all equations from left to right. That path has M*2^N nodes. The edges of the graph connect solutions that do not collide (i.e. where variables overlapping between solutions take the same value). Since only neighbouring equations overlap in their variables, the number of edges per node is some (not too large) constant. Finding such a path is now straight-forward and polynomial effort. see also here.

So for the riplets in this paper N is 3, so 2^N is a constant, leaving no exponential in the computational cost function. I hoped other people could comment on their impression of the paper, but as this is /. RTFA is not so common I guess :)

In fact it does suffice to show that the algorithm determines satisfiability of a 3-SAT instance in polynomial time. Create a derived 3-SAT instance that adds a clause restricting one variable to value '1'. Then see whether it is still satisfiable. It is not? Ok, constrain the variable to '0', and add a constraint for the next variable. Is it now satisfiable? And on and on. You understand the pattern? For n variables it only takes O(n) time to turn the 3-SAT satisfiability testing algorithm into a 3-SAT solver. Or in CS terms: the 3-SAT decision problem is polynomial time reducable to the 3-SAT solving problem.

• Integer factorization is not NP-hard (which would imply it is outside NP), it is in NP
• Being in NP, but not NP-complete means, that it is probaly "easier" then 3-SAT (look at this diagram describing relations between complexity classes)
• The discrete logarithm problem can be implemented via factorization and vice versa. If you can easily solve one, you can easily solve the other

Maybe I'm overlooking something, but to me it looks like they're doing the reduction to a polynomial-time problem already at the very beginning of the paper (I guess if there is a fault, there it hides). As soon as they go to "compact triplet" structure, the instance of 3-SAT is polynomial-time solvable using a trellis algorithm. Yes, very similar to the algorithm that is employed to decode convolutional codes.

In fact they're decomposing the initial 3-SAT problem into multiple "compact triplet" 3-SAT problems intersected using an AND operation. But as these intersected 3-SAT formulas use the same variables, without any interleaving (permutation) applied, the trellis algorithm still applies (just like solving for a convolutional encoder with > 1 check bits per bit).

Thinking once more about that: the compact triplet structure is clearly not general enough to express generic 3-SAT problems. This is like attempting to transform a quadratic optimization problem x^T*H*x involving a symmetric matrix H into a corresponding problem with a tri-diagonal matrix H.

The only way I see they could do the transform is by introducing exponentially many helper variables, thus moving the problem back into NP again. But it does not look like they're attempting something like that.