Class Description

CP: Continuous P

Same as CLOG, except that the convergence time can be polynomial rather than logarithmic in the input size.

Defined in [BSF02] and [SF98].

Finding a maximum flow, which is P-complete, can be done in CP [BSF02]. Based on this the authors argue that "P is contained in CP," but this seems hard to formalize, since CP is not a complexity class in the usual sense. They also conjecture that "CP is contained in P" (i.e. the class of ODE's they consider can be integrated efficiently on a standard Turing machine), but this is open.

Contained in CNP.

Linked From

CLOG: Continuous Logarithmic-Time

Roughly, the class of continuous problems solvable by an ordinary differential equation (ODE) with convergence time logarithmic in the size of the input. The vector field of the ODE is specified by an NC1 formula, with n parameters that represent the input. The point to which the ODE converges (assuming it does) is the output.

Defined in [BSF02], which should be consulted for more details.

[BSF02] show that finding the maximum of n integers is in CLOG. Thus, CLOG is best thought of as the continuous-time analog of NC1, not of DTIME(log n).

Contained in CP.

More about...


CNP: Continuous NP

A nondeterministic analog of CP. Defined in [SF98], which should be consulted for the definition (it has something to do with strange attractors, I think).

The authors raise the question of whether CP equals CNP.

More about...