The quest for all-optical signal processing is generally deemed to be impractical because optical nonlinearities are usually weak. The emerging field of nonlinear photonic crystals seems destined to change this view dramatically. Theoretical considerations show that all-optical devices using photonic crystal designs promise to be smaller than the wavelength of light, and to operate with bandwidths that are very difficult to achieve electronically. When created in commonly used materials, these devices could operate at powers of only a few milliwatts. Moreover, if these designs are combined with materials and systems that support electromagnetically induced transparency, operation at single-photon power levels could be feasible.