Regarding your next to last point, it seems like there has been some prior work involving statistical physics techniques in computational complexity theory; see e.g., http://cdsagenda5.ictp.it/full_display.php?ida=a01155.