Affiliations: Department of Computer Science, Shahid Beheshti University, G.C., Evin, Tehran, Iran
Correspondence:
[*]
Corresponding author. Hadi Farahani, Department of Computer Science, Shahid Beheshti University, G.C., Evin, Tehran, Iran. E-mail: h_farahani@sbu.ac.ir.
Abstract: We define a meta-type (MFTM) of Fuzzy Turing Machines (FTM) in which the transitions can take dynamic degrees corresponding with the input. The advantage of MFTM over other FTMs previously defined in the literature is that, by applying the dynamic degrees of transitions, it can resolve a deficiency in recognizing the fuzzy languages where their elements have arbitrary different non-crisp degrees. This results in recognizing a larger class of fuzzy languages than the other FTMs. Also, we establish a fuzzy theory of computational complexity and introduce two complexity classes FP and FNP for fuzzy polynomial time-bounded (deterministic and non-deterministic) computations. We propose fuzzy variants of three problems namely, finding a path (PATH) and a Hamiltonian path (HAMPATH) in a digraph and SAT problem. We show that the fuzzy variant of PATH is in FP while the ones of SAT and HAMPATH are in FNP. We introduce the class of FNP-complete problems and show that fuzzy variants of SAT, 3-SAT and HAMPATH are FNP-complete.
