Computational Complexity of Wavelength-Based Machine with Slightly Interacting Sets
Sama Goliaei and Mohammad-Hadi Foroughmand-Araabi
The wavelength-based machine is a computational model working with light and optical devices. Wavelength-Based machine assumes that it can breakdown light to several very small pieces and act on them simultaneously to achieve efficiency in computation. In this paper, first we introduce the wavelength-based machine. Then, we define two new operations: concentration and double concentration operations, which give the wavelength-based machine the ability to check the emptiness of one and two light rays. Both of the concentration and double concentration operations are implemented by white-black imaging systems. In this paper, we compare the computational power of P-uniform wavelength-based machines with and without concentration operations.
We show that polynomial size wavelength-based machines with concentration operation compute exactly NP languages, thus, adding the concentration operation, does not increase the computational power of wavelength-based machines. In contrast, polynomial time wavelength-based machines with concentration operation compute exactly PSPACE languages, however, polynomial time wavelength-based machines without concentration operations only compute NP languages.
Keywords: Unconventional computation, natural computing, optical computing, wavelength-based machine, concentration enabled w-machine, computational complexity