We introduce a restricted second-order logic $\textrm{SO}^{\textit{plog}}$ for finite structures where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. We demonstrate the relevance of this logic and complexity class by several problems in database theory. We then prove a Fagin’s style theorem showing that the Boolean queries which can be expressed in the existential fragment of $\textrm{SO}^{\textit{plog}}$ correspond exactly to the class of decision problems that can be computed by a non-deterministic Turing (...) machine with random access to the input in time $O^k)$ for some $k \ge 0$, i.e. to the class of problems computable in non-deterministic poly-logarithmic time. It should be noted that unlike Fagin’s theorem which proves that the existential fragment of second-order logic captures NP over arbitrary finite structures, our result only holds over ordered finite structures, since $\textrm{SO}^{\textit{plog}}$ is too weak as to define a total order of the domain. Nevertheless, $\textrm{SO}^{\textit{plog}}$ provides natural levels of expressibility within poly-logarithmic space in a way which is closely related to how second-order logic provides natural levels of expressibility within polynomial space. Indeed, we show an exact correspondence between the quantifier prefix classes of $\textrm{SO}^{\textit{plog}}$ and the levels of the non-deterministic poly-logarithmic time hierarchy, analogous to the correspondence between the quantifier prefix classes of second-order logic and the polynomial-time hierarchy. Our work closely relates to the constant depth quasipolynomial size AND/OR circuits and corresponding restricted second-order logic defined by David A. Mix Barrington in 1992. We explore this relationship in detail. (shrink)

L’Autore di questo libro è noto per le sue vitrioliche critiche al web e in generale alla comunicazione elettronica. Ma questo libro è la prova che non si tratta di neo-luddismo, vale a dire di una opposizione a priori all’innovazione tecnologica. L’Autore semplicemente richiama il dovere di valutare le “ricadute” del progresso tecnico, sia sociali che psicologico-individuali. L’eccesso delle informazioni, rapide e varie, può determinare una grave de-concentrazione, ansia immotivata, disorientamento. In questo libro si indicano le condizioni per un progresso (...) tecnico non alienante, in cui l’equilibrio fra ragione ed emotività sia garantita, in vista di un nuovo umanesimo. (shrink)

Ciò che in Weber grandeggia è il senso del problema, la consapevolezza problematica che si esprime in una serie di domande insistenti, che tornano come motivi di fondo in tutti i suoi scritti e cercano una verifica empirica, una base di validità intersoggettiva: perché gli uomini obbediscono? Quali sono le conseguenze dell’etica, intesa come etica vissuta, sul comportamento economico? In che senso è possibile conciliare le procedure standardizzate e impersonali della routine amministrativa con la decisione politica e l’innovazione tecnologica? Quale (...) sarà l’avvenire del capitalismo e del suo peculiare «spirito»? Che cosa accadrà al regno delle idee, ai grandi valori della tradizione liberale che costituiscono, secondo Weber, il nucleo della civiltà occidentale? (shrink)