The basic aim of soft computing is to trade precision for a tractableness and reduction in solution cost by pushing the limits of tolerance for imprecision and uncertainty. This paper introduces a novel soft computing technique called complex neutrosophic relation (CNR) to evaluate the degree of interaction between two complex neutrosophic sets (CNSs). CNSs are used to represent two-dimensional information that are imprecise, uncertain, incomplete and indeterminate. The Cartesian product of CNSs and subsequently the complex neutrosophic relation is formally defined. This relation is generalised from a conventional single valued neutrosophic relation (SVNR), based on CNSs, where the ranges of values of CNR are extended to the unit circle in complex plane for its membership functions instead of [0, 1] as in the conventional SVNR. A new algorithm is created using a comparison matrix of the SVNR after mapping the complex membership functions from complex space to the real space. This algorithm is then applied to scrutinise the impact of some teaching strategies on the student performance and the time frame(phase) of the interaction between these two variables. The notion of inverse, complement and composition of CNRs along with some related theorems and properties are introduced. The performance and utility of the composition concept in real-life situations is also demonstrated. Then, we define the concepts of projection and cylindric extension for CNRs along with illustrative examples. Some interesting properties are also obtained. Finally, a comparison between different existing relations and CNR to show the ascendancy of our proposed CNR is provided.