12 November 2020 in arXiv
Boolean satisfiability is a propositional logic problem of interest in multiple fields, e.g., physics, mathematics, and computer science. Beyond a field of research, instances of the SAT problem, as it is known, require efficient solution methods in a variety of applications. It is the decision problem of determining whether a Boolean formula has a satisfying assignment, believed to require exponentially growing time for an algorithm to solve for the worst-case instances. Yet, the efficient solution of many classes of Boolean formulae eludes even the most successful algorithms, not only for the worst-case scenarios, but also for typical-case instances. Here, we introduce a memory-assisted physical system (a digital memcomputing machine) that, when its non-linear ordinary differential equations are integrated numerically, shows evidence for polynomially-bounded scalability while solving "hard" planted-solution instances of SAT, known to require exponential time to solve in the typical case for both complete and incomplete algorithms. Furthermore, we analytically demonstrate that the physical system can efficiently solve the SAT problem in continuous time, without the need to introduce chaos or an exponentially growing energy. The efficiency of the simulations is related to the collective dynamical properties of the original physical system that persist in the numerical integration to robustly guide the solution search even in the presence of numerical errors. We anticipate our results to broaden research directions in physics-inspired computing paradigms ranging from theory to application, from simulation to hardware implementation.
20 September 2019 in arXiv
We develop a general model for finding the optimal penal strategy based on the behavioral traits of the offenders. We focus on how the discount rate (level of time discounting) affects criminal propensity on the individual level, and how the aggregation of these effects influences criminal activities on the population level. The effects are aggregated based on the distribution of discount rate among the population. We study this distribution empirically through a survey with 207 participants, and we show that it follows zero-inflated exponential distribution. We quantify the effectiveness of the penal strategy as its net utility for the population, and show how this quantity can be maximized. When we apply the maximization procedure on the offense of impaired driving (DWI), we discover that the effectiveness of DWI deterrence depends critically on the amount of fine and prison condition.