"

Cookies ussage consent

Our site saves small pieces of text information (cookies) on your device in order to deliver better content and for statistical purposes. You can disable the usage of cookies by changing the settings of your browser. By browsing our site without changing the browser settings you grant us permission to store that information on your device.

I agree, do not show this message again.

Optical solutions for linear Diophantine equations

O. MUNTEAN1,* , M. OLTEAN1

Affiliation

  1. Department of Computer Science, Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Kogălniceanu 1, Cluj-Napoca, 400084, Romania

Abstract

Determining whether a Diophantine equation has a solution or not is the most important challenge in solving this type of problems. In this paper a special computational device which uses light rays is proposed to answer this question, namely check the existence of nonnegative solutions for linear Diophantine equations. The way of representation for this device is similar to an directed graph, having a number of nodes equal to the number of variables of the equation plus the destination node. The arcs connecting these nodes have assigned a number (length) which corresponds to coefficients of the equation or it is a predefined constant. The light traversing the device follows all possible routes. In each arc it will be delayed by an amount of time indicated by the length of that arc. At the destination node, if a light ray arrives at the moment equal to the free term of the equation plus some constants we may infer that the equation has solution, otherwise it has not..

Keywords

Optical computing, Diophantine equations, NP-complete problems.

Submitted at: Nov. 1, 2009
Accepted at: Nov. 19, 2009

Citation

O. MUNTEAN, M. OLTEAN, Optical solutions for linear Diophantine equations, Journal of Optoelectronics and Advanced Materials Vol. 11, Iss. 11, pp. 1728-1734 (2009)