Titlebook: Gems of Theoretical Computer Science; Uwe Schöning,Randall Pruim Book 1998 Springer-Verlag Berlin Heidelberg 1998 Kolmogorov complexity.Re

恶臭

LOGSPACE, Random Walks on Graphs, and Universal Traversal Sequences,There is a surprising, at first glance unexpected, difference in (space) complexity between the problems of finding a path from a start node to an end node in a directed graph and of doing so in an undirected graph. In an undirected graph this is easier to solve; in fact, in can be done using a random walk or a universal traversal sequence.

Armory

NAUT

Spectral Problems and Descriptive Complexity Theory,This chapter begins with a question from predicate logic, namely to determine the set of all (sizes of) finite models of a given formula. It turns out that there is an amazingly close relationship between this question and the world of P and NP.

控制

DEBT

progestogen

Lower Bounds for the Parity Function,In their pioneering work of 1984, Furst, Saxe and Sipser introduced the method of “random restrictions” to achieve lower bounds for circuits: The parity function cannot be computed by an AND-OR circuit of polynomial size and constant depth.

condone

Foreshadow

孤独无助

The Berman-Hartmanis Conjecture and Sparse Sets,If all NP-complete languages were P-isomorphic to each other, then it would follow that P ≠ NP. This “Isomorphism Conjecture” has been the starting point of much research, in particular into sparse sets and their potential to be NP-complete.

牲畜栏