Logic as Machine: Complexity Relations between Programs and Formulae