2014/08/03 by Feng Pan, Pan, Feng, Heng-Liang Zhang +3
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #Data Analysis #FOS: Computer and information sciences #FOS: Physical sciences #Statistical Mechanics (cond-mat.stat-mech) #Statistics and Probability (physics.data-an) #cond-mat.stat-mech #cs.CC #physics.data-an
paper · pdf · doi:10.48550/arxiv.1408.0445
10 pages, 1 figure
arxiv created 2014/08/03 · arxiv updated 2014/08/06
In this paper two connected Szilard single molecule engines (with different temperature) model of Maxwell's demon are used to demonstrate and analysis the logical compare operation. The logical and physical complexity of compare operations are both showed to be kTln2. Then this limit was used to prove the time complexity lower bound of sorting problem. It confirmed the proposed way to measure the complexity of a problem, provided another evidence of the equivalence between information theoretical and thermodynamic entropies.