Exact phase transition of backtrack-free search with implications on the power of greedy algorithms

Backtracking is a basic strategy to solve constraint satisfaction problems (CSPs). A satisfiable CSP instance is backtrack-free if a solution can be found without encountering any dead-end during a backtracking search, implying that the instance is easy to solve. We prove an exact phase transition of backtrack-free search in some random CSPs, namely in Model RB and in Model RD. This is the first time an exact phase transition of backtrack-free search can be identified on some random CSPs. Our technical results also have interesting implications on the power of greedy algorithms, on the width of random hypergraphs and on the exact satisfiability threshold of random CSPs.

Quantum random number generator based on the photon number decision of weak laser pulses

We propose an approach to realize a quantum random number generator (QRNG) based on the photon number decision of weak laser pulses. This type of QRNG can generate true random numbers at a high speed and can be adjusted to zero bias conveniently, thus is suitable for the applications in quantum cryptography.

From k-SAT to k-CSP: Two Generalized Algorithms

Constraint satisfaction problems (CSPs) models many important intractable NP-hard problems such as propositional satisfiability problem (SAT). Algorithms with non-trivial upper bounds on running time for restricted SAT with bounded clause length k (k-SAT) can be classified into three styles: DPLL-like, PPSZ-like and Local Search, with local search algorithms having already been generalized to CSP with bounded constraint arity k (k-CSP). We generalize a DPLL-like algorithm in its simplest form and a PPSZ-like algorithm from k-SAT to k-CSP. As far as we know, this is the first attempt to use PPSZ-like strategy to solve k-CSP, and before little work has been focused on the DPLL-like or PPSZ-like strategies for k-CSP.

On Exponential Time Lower Bound of Knapsack under Backtracking

M.Aleknovich et al. have recently proposed a model of algorithms, called BT model, which generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model by Woeginger. BT model can be further divided into three kinds of fixed, adaptive and fully adaptive ones. They have proved exponential time lower bounds of exact and approximation algorithms under adaptive BT model for Knapsack problem. Their exact lower bound is $Omega(2^{0.5n}/sqrt{n})$, in this paper, we slightly improve the exact lower bound to about $Omega(2^{0.69n}/sqrt{n})$, by the same technique, with related parameters optimized.