the description of a problem that requires polynomial time, then that compressed problem would require exponential time.

As one example, some graphs can be succinctly described by a small Boolean circuit. The circuit has inputs, 1 output and gates, thus requiring bits to describe. The circuit represents a graph with vertices. For each pair of vertices, if the binary code for the two vertices are put into the circuit, then the output of the circuit states whether the two vertices are connected by an edge.

For many naturally

1.Previous
3.Next