<figure><img src="image_1.png" /></figure>

HAL
open science

# Theory of Fuzzy Time Computation(TC * vs TC, TQC)

farzad didehvar

► To cite this version:

farzad didehvar. Theory of Fuzzy Time Computation(TC * vs TC, TQC). 2023. [https://hal.science/hal-04330281v1](https://hal.science/hal-04330281v1)

HAL Id: hal-04330281

Preprint submitted on 7 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Theory of Fuzzy Time Computation(TC* vs TC, TQC)

Farzad Didehvar

didehvar@aut.ac.ir

Amir Kabir University of Technology (Tehran Polytechnic)

January 1 2023

**Abstract.** One of the possible hypotheses about time is to consider any instant of time as fuzzy number, so that two instants of time could be overlapped. Historically, some Mathematicians and Philosophers have had similar ideas like Brouwer and Husserl [5].

Throughout this article, the impact of this change on Theory of Computation and Complexity Theory are studied.

In order to rebuild Theory of Computation in a more successful and productive approach to solve some major problems in Complexity Theory, the present research is done. This novel theory is called here, the fuzzy time theory of computation, TC*. Here, we show the situation of some major problems in Complexity theory and Quantum computation.

**Keywords.** P ≠ NP, P = PBB, MA = AM, PH ⊊ PSPACE, QIP=PSPCE, QMA* = MA* = AM* = QAM*(= QMA = QAM), Fuzzy Time, TC*, Reducibility, Complexity Theory Problems, Fuzzy time particle interpretation of Quantum mechanics

## 1. Introduction

Throughout this article, the author presents the Theory of Computation by applying Fuzzy Time. More specifically, the author tries to rebuild the structure of the Theory of computation based on considering time as a fuzzy concept.

In fact, there are reasons to believe time as a fuzzy concept. More precisely, here, given the classical definition of Turing Machine, the concept of Time is changed to be Fuzzy. This new theory is called Theory TC* and this type of computation "Fuzzy time Computation". We have relatively large number of fundamental unsolved problems in Complexity Theory. In the new theory, some of the major obstacles and unsolved problems have been solved. It should be noted that in this article, the author considers fuzzy number associated to instants of time as a
symmetric one. The point is, applying the symmetricity of fuzzy time function in
the proof of Lemma 3.

In particular, the new classes of complexity Theory, P*, NP*, BPP* in the TC* are
defined similar to the definitions of P, NP and BPP as their natural alternative
definition. Here, firstly we prove, P* = BPP*, MA* = AM*. Later we presnt some
results about P vs NP problem and PH vs PSPACE problem in the new model.
Finally, we discuss about Quantum Complexity classes.

Considering instants of time as fuzzy concept has some excuses which we list
them as following

1. Brower and Husserl had similar ideas [5]. Also, some physicists introduced the operator of time.

2. There is no reason right now, to prefer Classical time to a model of time which fuzzy time function is a narrow function.

3. By a new interpretation of Quantum Mechanics we are able to compute the fuzzy instants of time.[6]

Moreover, there is a possibility to understand experimentally whether time
is a fuzzy concept.[7]

This means this fuzzy time is in harmony with the modern concepts of
Physics.

4. Besides all, we have a more easygoing and feasible theory based on this hypothesis (TC*), as we explain in this article.

5. By this, We have a solution for some paradoxes like “Unexpected hanging paradox”.[8]

6. In this paper we will see, even in the case that considering fuzzy time as a physical concept doesn't seem appropriate, this consideration theoretically would be useful. Roughly speaking, by applying this technic we are capable to solve some problems in TC.

It should be noted that the main theoretical streamline in this article as,
considering the contrast betweenTC, TC* is useful to solve some major
questions in the field setting of Complexity theory. However, it is possible
that physically TC* would be a better choice. In general, this provides a
novel approach to start studying theory of Computation.
Some part of this theory was introduced in [17], [18], [19].

# 1. The spaces and model of computation

To have an exact proof, first we define $W_m$. Let Type equation here.

$$W_m = \{C_{i,t} \stackrel{m}{\Rightarrow} C_{j,t}: C_{i,t} \text{ & } C_{j,t} \text{ are configurations for } M_t, m \in N\}$$

Now, we define $C \subseteq W_m$ as follows

$$C = \{C_{i,t} \stackrel{m}{\Rightarrow} C_{j,t}: C_{i,t} \text{ & } C_{j,t} \text{ are configurations for } M_t \text{ and in } m \text{ steps}\}$$

by transition function associated to $M_t$, we reach from $C_{i,t}$ to $C_{j,t}$ (Classical computational world)

We define $\circ$ on $W_m$

$$\circ: W_m \times W_m \rightarrow W_m$$

$$(C_{i,t} \stackrel{m}{\Rightarrow} C_{j,t}) \circ (C_{j,t} \stackrel{n}{\Rightarrow} C_{k,t}) = (C_{i,t} \stackrel{m+n}{\Rightarrow} C_{k,t})$$

Furthermore, $C$ induces a directed graph on the space of all configurations, like $\vec{G}$. We call the underlying graph of this undirected graph, $G$.

(Remark1. In the case of nondeterministic Turing Machines, we define the concepts in the same way.)

By considering, fuzzy time, we have the possibility of turning back in time. So, any path in the graph $G$, is a path of possible computation, when in our model we consider instants of time as fuzzy number.

In the definition of path here, the nodes could be repeated but the lengths of paths are finite. $P(G)$ is the set of all paths of $G$.

$$W_{\text{FUZZY}} = \{C_{i,t} \stackrel{m}{\Rightarrow} C_{j,t}: m \in N, C_{i,t} \text{ & } C_{j,t} \text{ belong to a path in } P(G)\}$$

We call $W_{\text{FUZZY}}$ the Fuzzy world. In the fuzzy world, all of these paths are possible.
Here, any instant of time is a fuzzy number, which its support is $R$, the set of real numbers.

**Remark 1.** Here, we are able to define the “fuzzy computational model” more exactly, in the case that the area under the instant of time is finite.

Computational-

Model= {($C_{i,t} \Rightarrow^m C_{j,t}$, $\eta(C_{i,t} \Rightarrow^m C_{j,t})$): $m \in \mathbb{N}$, $C_{i,t}$ & $C_{j,t}$ belong to a path in $P(G)$, $\eta(C_{i,t} \Rightarrow^m C_{j,t})$ is the probability

of reaching from $C_{i,t}$ to $C_{j,t}$ in m steps}

$\eta$ could be computed by fuzzy function

**Corollary 1.** If we consider quantum computers instead of non deterministic Turing machines we have the same definitions. It will lead us to a unification of these two theories. In the other words, it is easy to see that, by considering Fuzzy time-particle Interpretation of quantum Mechanics, TC*, TQC and

TQC* are the same theories, and the respected Complexity classes are equal sets. In the last chapter, we will show some results by considering this interpretation of quantum mechanics.

## 2. Reducibility

In this section, firstly, we define a quasi-order relation in TC* analogous with the m-reducibility in TC.

It should be reminded that a fuzzy time Turing Machine is a Turing Machine which works with fuzzy time, as it is defined in the previous section.

In addition, here, the Turing Machine is considered as a two tuple $(M, S)$. Whereas, $M$ is a Turing machine in the usual sense and $S$ is a polynomial function. Meanwhile, $M$ runs in bounded time by $S$, equivalently, $M(x)$ in less than $S([x])$ steps is computed.

First, we remind the Classical definition of m-reducibility:

$Y >_{m} X$, if there is a polynomial time computable function $f$ such that:
$$x \in X \leftrightarrow f(x) \in Y$$

The parallel definition in TC* is introduced as following

**Definition 1:** For $\alpha > \frac{1}{2}$, $Y >_{m}^{\alpha} X$ if there is a polynomial time computable* function f such that:

1. $x \in X \& f(x) \downarrow$ in polynomially bounded time respect to $|x| \leftrightarrow (f(x) \in Y)$

2. Pr($f(x) \downarrow$ in polynomially bounded time respect to $|x| > \alpha$)

A Computable* function f is a function that is computable by a fuzzy time Turing machine.

Here, by bounded time, we mean that for the function f there exists a Polynomial function h such that $f(x) \downarrow$ in less than h (length(x)) steps.

$Y >_{m}^{\alpha} X$ can be represented by a 5-tuple, $(Y, X, f, S_f, \alpha)$, $S_f(x)$ is the number of steps that $f(x)$ is computed. The definition is as follows

$$Y >_{m}^{\alpha} X \leftrightarrow (Y, X, f, S_f, \alpha) \text{ is an acceptable 5-tuple}$$

One of the major question here is about the independence of the definition from the value of $\alpha$? ($\alpha > \frac{1}{2}$)

In the first step, to answer the above question, we need the following simple lemma.

**Lemma 1** Let for $1 > \alpha > \frac{1}{2}$, $(Y, X, f, S_f, \alpha)$ is an acceptable 5-tuple then for any $1 > \beta > \frac{1}{2}$ there is a computable function g in which $(Y, X, g, S_g, \beta)$ is an acceptable 5-tuple.

**Proof.** Actually, there is a natural number $k$, so that the function g is equivalent to, $k$ times repeating $f$, till we reach a solution with probability less than $\beta$. It is easy to understand that such $k$ exists. $\square$

Lemma 1 indicates for $1 > \alpha > \frac{1}{2}$, the relation $Y >_{m}^{\alpha} X$ would be independent of $\alpha$. So, we define $Y >_{m}^{*} X$ as follows
**Definition 2.** $Y >_{m}^{*} X$ if for some $\alpha (1 > \alpha > \frac{1}{2})$, $Y >_{m}^{\alpha} X$.

**Lemma 2.** $>_{m}^{*}$ is a quasi-order relation.

**Proof.** $X >_{m}^{\alpha} Y$ implies $\forall \frac{1}{2} > \varepsilon > 0 \ X >_{m}^{1-\varepsilon} Y (*)$

$Y >_{m}^{\alpha} Z$ implies $\forall \frac{1}{2} > \varepsilon > 0 \ Y >_{m}^{1-\varepsilon} Z (**)$

From (*), (**), we have $\forall \frac{1}{2} > \varepsilon > 0 \ X >_{m}^{(1-\varepsilon)^2} Y (***)$. $\square$

**Lemma 3.** $Y >_{m} X$ implies $Y >_{m}^{*} X$.

**Proof.** First, we remind that, throughout this article the associated fuzzy numbers to the instants of time are symmetric.

We have computable function $f$ such that

$$x \in X \leftrightarrow f(x) \in Y$$

$f$ is associated with a Turing machine, ($M, S_f$). The computation of $f(x)$ can be depicted by the transition of configurations in time in $S_f(x)$ steps, to reach the final configuration.

Now, as mentioned above, the concept of time is changed to be fuzzy. So, the probability of reaching or passing the final configuration is higher than the probability of not to reach this point.

According to the rules of probability and the above comments, the probability of reaching or passing the final configuration is more than $\frac{3}{4}$ and the probability of not to reach the final configuration is less than $\frac{1}{4}$, if we consummate $2S_f(x)$ units of time. Likewise, by consumption of $p S_f(x)$ units of time, the probability of reaching the final configuration or passing it, is more than $1 - \frac{1}{2^p}$ and the probability of not to reach this final configuration is less than $\frac{1}{2^p}$. So, we have, $Y >_{m}^{*} X$. $\square$
**Remark 2.** Using lemma 3, suppose we have a computation by Turing Machine $(M, S_f)$ and the input $x$ in classical time and $(M, S_f)(x) \downarrow$. If we change the classical time to the symmetric fuzzy time, the probability of reaching to the final state is more than $\frac{1}{2}$. As a conclusion, if we consider the computation $(M, k S_f)(x) \downarrow$, the probability of reaching to the final state is more than $1 - \frac{1}{2^k}$.

## 2.2 $P^*, NP^*, NP^* - \text{Hard}, NP^* - \text{Complete}$

One of the main questions throughout this article is, how to redefine the most important classes of Complexity Theory in the new theory? As a first attempt, let us try to define $P^*$ as follows:

$P^*$ is the class of all problems that can be determined by a Fuzzy Turing Machine $(M, S)$.

But what exactly do we mean by determined? Since it is possible that we do not reach to the final state, we should consider the possibility associated with $x \in p$ for any $p \in P^*$ when $x$ belongs to $p$, and the possibility associated with $x \notin p$ when $x$ belongs to $p^c$. Hence, by the above consideration, we are able to modify the definition of $P^*$, as follows

**Definition 3.** $P^*$ is a class of problems such that, for any $p \in P^*$ and the probability $\alpha$, we have a polynomial $Q_{\alpha,p}$ and an associated algorithm $A_{\alpha,p}$ to solve $p$ by probability $\alpha$ such that $Q_{\alpha,p}$ is upper bound of the computation time. Equivalently, for any $p \in P^*$ ($p$ as a language) and probability $\alpha$ we have an associated algorithm $B_{\alpha,p}$ and a polynomial $Q_{\alpha,p}$ as an upper bound of the computation time.

$x \in p \rightarrow$ By probability $\alpha$, $B_{\alpha,p} = 1$

$x \notin p \rightarrow$ By probability $\alpha$, $B_{\alpha,p} = 0$

This is similar to the definition of the class BPP. Equivalently, by considering time as a Fuzzy concept we have $BPP^*$.

By the above considerations, it is easy to see:

**Theorem 1.** $P^* = BPP^*$.
The next natural question in TC* is the situation of the problem P vs NP, more
exactly P* vs NP*. Firstly, we are going to prove the following proposition about
random generators.

**Proposition1.** By considering time as a fuzzy concept, random Generators exist.

**Proof.** Introducing the following algorithm demonstrates that there is a random
generator. It is sufficient to consider an algorithm such that in interval times
$[2n, 2n + 1]$, it emits as an output 0 and in interval times $[2n + 1, 2n + 2]$, it
emits 1, when time is considered as a classical concept. Now by considering time
as a fuzzy concept, it is easy to see that we have a random number generator.
More exactly, by considering fuzzy instant of time as fuzzy number we have
probability function $p(x)$, $1 > p(x) > 0$, in a way that for any real number $X + t$
such that $1 > t > 0$ and $X$ is a natural number

If X is an odd number by probability p(t), in X + t, the algorithm emits 1 (p(t) is
near to 1!)

If $X$ is an even number by probability $p(t)$, in $X + t$, the algorithm emits 0 ($p(t)$ is near to 1!)

Clearly, $p(x): R \rightarrow [0,1]$ is a periodic function. By this probability function, we are
able to produce the random generator. $\square$

Now, let we consider the following definition of NP problems.

**Definition 4** The Complexity class **NP** is the set of decision problems like D such that there is a deterministic polynomial time Turing machine $M_D$ and polynomials $p_D, q_D$ in order that for every input $x$ with length $x'$ ($1(x)=x'$)

1. $x$ belongs to D implies there exists string $z$ with length $q_D(x')$ such that for all string $y$ with length $p_D(x')$, $\Pr(M_D(x, y, z) = 1) = 1$)

2. $x$ does not belong to D implies for all string $z$ with length $q_D(x')$ such that for all string $y$ with length $p_D(x')$, $\Pr(M_D(x, y, z) = 0) = 1$ (The definition is Quoted in [4])

By considering the above definition and by fuzzifying time we have the definition
of NP*.

We define NP*--hard, NP*-Complete likewise in below

**Definition 5** X is NP*-hard if for any $Y \in NP^*$, $X >_m^* Y$.
**Definition 6** X is NP\*-Complete if X is NP\*-hard and $X \in NP\*$.

**Theorem 2** SAT is NP\*-Complete.

**Proof.** SAT belongs to NP, hence SAT $\in NP\*$, by definition. The analogues proof of Cook-Levin's theorem works here. More exactly, by employing the reduction associated with the reduction function $f$ in Cook-Levin theorem with this difference that time is fuzzy, we have the analogous function $f^*$ in the new proof, also here, we consider $>_{m}^*$ instead of $m$-reducibility. Lemma 3 guarantees the proof of the theorem. $\square$

**Theorem 3.** $P^* \neq NP^*$ implies $P \neq NP$.

**Proof.** To prove $P \neq NP$, we apply Theorem 2 and lemma 3.

Suppose $P = NP$ and we remind that SAT is a NP-Complete problem. Hence, there is an algorithm $A$ which solves SAT in Polynomial time.

Considering Fuzzy time, $A$ also solves SAT in polynomial time, hence SAT belongs to $P^*$. SAT is NP\*-Complete, so $P^* = NP^*$. A contradiction. Consequently, $P \neq NP$. $\square$

**Lemma 4.** $SAT \notin P$ implies $SAT \notin P^*$, unless $P = NP$.

**Proof.** SAT is NP\*-Complete. Suppose $SAT \notin P$. If $SAT \in P^*$ then $P^* = NP^*$. In brief, $P \neq NP$ implies $P^* = NP^*$, which is a contradiction by Theorem 3. $\square$

**Theorem 4.** $P \neq NP$ implies $P^* \neq NP^*$.

**Proof.** Suppose $P \neq NP$. By above lemma, $P \neq NP$ implies $SAT \notin P^*$. But $SAT \in NP^*$, so $P^* \neq NP^*$. $\square$

**Chapter 3.** $MA^*, AM^*$

In the previous chapter, by defining the concepts of $P$, $BPP$ in the new framework, we define the new classes $P^*, BPP^*$. It is shown that the new classes $P^*, BPP^*$ are both equal to each other. In contrast, what is the alternative definition for the NP class in this new framework? To illustrate NP problems in
the Theory of Algorithm, it is required to define a new class for it. Possibly MA is the best choice in probabilistic classes [1], [4] (introduced by Laszlo Babai, Shafi Goldwasser, Micheal Sipser).

Indeed, the MA complexity class is known as an alternative for NP problems in probabilistic classes, we also have a theorem states [2], [3]

$$P = BPP \rightarrow MA = NP$$

The last point, besides $P^* = BPP^*$ confirms our choice. So, let we define the concept of NP problems in fuzzy time by applying and similar to the definition of MA. On the other hand in the previous chapter we defined NP*, as the second way to define an alternative definition for NP in TC*. It is easy to see, these two ways of defining a parallel concept for NP in TC*, leads us to the equivalent definitions.

Here, we mention the complexity class Merlin-Arthur MA, in Two-sided version definition [4].

**Definition 7.** The Complexity class **MA** is a set of decision problems like D such that there are

deterministic polynomial time Turing machine $M_D$ and polynomials $p_D, q_D$ in order that for every input $x$ with length $x'$ ($l(x)=x'$)

1. $x$ belongs to D implies there exists string $z$ with length $q_D(x')$ such that for all string $y$ with length $p_D(x')$ $Pr(M_D(x, y, z) = 1) \ge 2/3$)

2. $x$ does not belong to D implies for all string $z$ with length $q_D(x')$ such that for all string $y$ with length $p_D(x')$ $Pr(M_D(x, y, z) = 0) \ge 2/3$ (The definition is Quoted in [4])

Likewise, we remind the complexity class Arthur-Merlin AM in Two-sided version definition [4].

**Definition 8.** The Complexity class **AM** is a set of decision problems like D such that there are deterministic polynomial time Turing machine $M_D$ and polynomials $p_D, q_D$ in order that for every input $x$ with length $x'$ ($l(x)=x'$)
1. x belongs to D implies there exists string z with length $q_D(x')$ such that for all string y with length $p_D(x')$ $\Pr(M_D(x, y, z) = 1) \ge 2/3$

2. x does not belong to D implies for all string z z with length $q_D(x')$ such that $\Pr(\text{for all string y with length } p_D(x'), M_D(x, y, z) = 0) \ge 2/3$ (The definition is Quoted in [4])

By considering time as a fuzzy concept, we define $MA^*$. $AM^*$ is defined similarly, by considering two sided definition of AM in above.

The list of new possible classes which we study here, is $P^*, NP^*, BPP^*, MA^*, AM^*$ and $AM^*$.

Instead of $P = NP$ problem and in parallel to it, we have the following problems

$$BPP^* = MA^*$$

$$BPP^* = AM^*$$

$$MA^* = AM^*$$

Theorems 3&4 shed a light on the above problems.

It is easy to see:

1. $P^* = BPP^*$ (Theorem 1)

2. $NP^* = MA^*$ (Considering certificate definition of NP)

It is notable to remind, by proposition 1, we have random generators in the new Theory. So, the pseudo-random generators exist too. In addition, we have $P^* = BPP^*$ (Theorem 1). In this theory the third major conclusion is about the classes $MA^*, AM^*$.

**Theorem 5.** $MA^* = AM^*$.

**Proof.** MA is the nondeterministic version of BPP, AM is the probabilistic version of NP.

So, clearly $AM^* = NP^*$ and $MA^*$ is the nondeterministic version of $BPP^*$.
By the way, $P^* = \text{BPP}^*$. Consequently, $\text{MA}^*$ is the nondeterministic version of $P^*$. By definition, $\text{MA}^* = \text{NP}^*$. In sum, $\text{AM}^* = \text{MA}^* = \text{NP}^*$. $\square$

Moreover, by above we have

**Theorem 6.** The following statements are equivalent

1. $P \neq \text{NP}$

2. $P^* \neq \text{NP}^*$

3. $\text{BPP}^* \neq \text{MA}^*(= \text{AM}^*)$

**Proof.** By Theorems 2, 3, 4, 5. $\square$

**Conclusion 1.** Throughout this Chapter, it is shown that by considering time as a fuzzy concept, we have random generators. Under this condition, $\text{TC}^*$ as a new theory in the field setting of computation is introduced. Hereafter, in the new theory, some problems in parallel to some of the famous problems in Complexity Theory are solved. In brief, $P^* = \text{BPP}^*$, $\text{MA}^* = \text{AM}^*$.

**4. Complexity Classes, $\text{TC} + \text{CON}(\text{TC}^*) \vdash P \neq \text{NP}$, $P = \text{BPP}$**

In this section first we present some definitions mostly based on the concepts introduced in the first section, in the second step we define some complexity classes, in the third step we give the proof of the above claims.

Now we define $R(M_t)$ as the set of possible computational worlds for turing machine $M_t$.

In section 1, we define $W_{\text{FUZZY}}$, Computational Model, here we continue to introduce the definitions related to the possible worlds associated to fuzzy time.

Let $R(M_t) = \{ W_{i,t} \}_{i \in I}$, which the following four conditions hold

1. $W_{i,t} \subset W_{\text{FUZZY}}$

2. $\forall m(C_{l,t} \stackrel{m}{\Rightarrow} C_{j,t} \in W_{i,t})$ implies there is a path between $C_{i,t} \& C_{j,t}$ in $W_{\text{FUZZY}}$

3. $C_{l,t} \stackrel{m}{\Rightarrow} C_{j,t} \in W_{i,t} \& C_{l,t} \stackrel{m}{\Rightarrow} C_{k,t} \in W_{i,t}$ implies $k = j$

4. $W_{i,t}$ is closed by $\circ$.
**Examples:**

1. $\{C_{0,t} \stackrel{m}{\Rightarrow} C_{0,t}: m \in \mathbb{N}\} \in \mathbb{R}(M_t)$, void world.

2. $C_{l,t} \stackrel{m}{\Rightarrow} C_{j,t} \in W_{c,t}$ iff $C_{l,t} \stackrel{m}{\Rightarrow} C_{j,t}$ in classical time in Turing machine $M_t$. $W_{c,t}$ is the classical world associated to $M_t$.

2. In the case of Non determinism, we do not consider the third condition in above.

Now, we define $S = \{(w_{i,t})_{t \in \mathbb{N}}: W_{i,t} \in \mathbb{R}(M_t)\}$, and we recall it the possible worlds of computation. We give here two members of $S$ as examples.

1. Void world of computation. $V \in S$ is Void world of computation by definition if any component of $V$ is a void world.

2. Classical world of computation. $W_{classical} \in S$ is classical world by definition, if any component of $V$ is a classical world.

**Definition 9.** The problem $X$ is solved by $W_{k,t}$ in polynomial time means, for some polynomial function $p$ and in less than $p(|a|)$ steps we have either 1 as output if a belongs to $X$ or we have 0 as output if a does not belong to $X$.

**Definition 10.** The problem $X$ is solved\_1 by $W_{k,t}$ in polynomial time means, for some polynomial function $p$ and in less than $p(|a|)$ steps, if a belongs to $X$ we have either 1 as output with a probability greater than or equal $2/3$

or if a does not belong to $X$ we have 0 as output with probability less than or equal $1/3$.

**Definition 11.** For $W_k \in S$, $X \in (P, W_k)$ or $X$ is a $(P, W_k)$ problem if $X$ is solved by $W_{k,t}$ in polynomial time, which $W_{k,t}$ is a component of $W_k$.
**Definition 12.** For $W_k \in S$, $X \in (BPP, W_k)$ or $X$ is a (BPP, $W_k$) problem if $X$ is solved_1, by $W_{k,t}$ in polynomial time, which $W_{k,t}$ is a component of $W_k$.

**Definition 13.** $X \in (NP, W_k)$, if for some polynomial function $Q$ there is a set $Y = \{(x, a): x \in X, |a|$ is less than $Q(|x|)\}$, such that $Y \in (P, W_k)$.

**Remark 3.** In the case $W_k = W_{classical}$, it is easy to see that, the above definition is equivalent to the following definition

**Definition 14.** $X \in (NP, W_{classical})$, if $X$ is solvable by non deterministic Turing machine in polynomial time.

Actually, $X \in (NP, W_{classical})$ if and only if $X \in NP$ and $X \in (P, W_c)$ iff $X \in P$.

**Poposition 2.** $X \in (P, W_{classical})$ iff $X \in P$.

**Poposition 3.** $X \in (BPP, W_{classical})$ iff $X \in BPP$.

**Poposition 4.** $X \in (NP, W_{classical})$ iff $X \in NP$.

**Poposition 5.** $SAT \in (P, W_{classical})$ then $P = NP$.

The concepts $m$-reucibility and $(NP, W_{classicl})$ - compelte is defined similar to the classical case.

**Poposition 6.** $X \in (NP, W_{classical})$ - complete iff $X \in NP$ - complete.
The concepts like seed and pseudorandom generator are defined analogous with the classical definition.

**Corollary 2.** If pseudo random generator exists, ($P, W_{classical}) \neq (NP, W_{classical})$, (i.e $P \neq NP$).

**Proof.** If $P = NP$ we are able to guess the seeds non deterministically, so pseudo random generator does not exist. $\square$

**Corollary 3.** If pseudo random generator exists, ($P, W_{classical}) = (BPP, W_{classical})$.

**Proof.** In above, $X \in (BPP, W_{classical})$ iff $X \in BPP$.

$W_{classical}$ is similar to the classical world of computation, nevertheless time is a fuzzy concept. Due to fuzziness of time in this model of computational world, we have random generator, consequently ($P, W_{classical}) \neq (NP, W_{classical})$, ($P, W_{classical}) = (BPP, W_{classical})$. $\square$

By the above proposition we have the following corollary.

**Corollary 4.** $P \neq NP$.

**Corollary 5.** $P = BPP$.

**Conclusion 2.** In the above proof, our presumption is the existence of a model for $TC^*$. So we have, $TC + \text{CON}(TC^*) \notin NP, P = BPP$.

Therefore, we have $P \neq NP$ so we have $P^* \neq NP^*$, $P^* = BPP^*$ [17], [2] under the same assumption.

**Generlization 1.** In above, for some specific formulas $\varphi$, (here $P \neq NP$ and $P = BPP$),

$TC + \text{Existence of random generator} \vdash \varphi$ implies

$TC + \text{CON}(TC^*) \vdash \varphi$.
In the first type of generalization, we try to show the type of sentences has the above property.

Firstly, we modify slightly our definitions, we used

$$C_{i,t} \stackrel{m}{\Rightarrow} C_{j,t}$$

As, possibility of reaching from on configuration to another in *m* steps. Now we write a similar and more complete form of this definition by

$$C_{i,t}(<x_{i,t}>) \stackrel{m}{\Rightarrow} C_{j,t}(<y_{j,t}>)$$

$x_{i,t}, y_{j,t}$ are two vectors which shows the data on the strip of Turing Machine, in configurations $C_{i,t}, C_{j,t}$.

Indeed, we define the usual Complexity classes in four groups, as following

1. Computably numerable set, Computable set

2. P,NP,...

3. Probability Classes.

4. Interactive proofs

We should enrich the language little by little to capture the concepts in the above four levels. Hence, we create the languages $\Sigma_1, \Sigma_2, \Sigma_3, \Sigma_4$, associated to these four levels.

1. $\Sigma_1$:Computably enumerable set, Computable set

$$x \in L \rightarrow \exists m C_{i,t}(<x_{i,t}>) \stackrel{m}{\Rightarrow} C_{j,t}(<y_{j,t}>) \& (x_{i,t} = x) \& (C_{i,t}(<x_{i,t}>) \text{ is a start configuration}) \& (C_{j,t}(<y_{j,t}>) \text{ is a final configurattion}) \& (<y_{j,t}> = 1)$$

$$x \notin L \rightarrow \exists m C_{i,t}(<x_{i,t}>) \stackrel{m}{\Rightarrow} C_{j,t}(<y_{j,t}>) \& (x_{i,t} = x) \& (C_{i,t}(<x_{i,t}>) \text{ is a start configuration}) \& (C_{j,t}(<y_{j,t}>) \text{ is a final configurattion}) \& (<y_{j,t}> = 0)$$

We need three relations, start configuration, final configuration, $C_{i,t}(<x_{i,t}>) \stackrel{m}{\Rightarrow} C_{j,t}(<y_{j,t}>)$ in our language.

It shapes first type of languages.
1. $\Sigma_2$:P, NP, ...

For P we are able to add a new quantifier bounded one... $\exists m < p(|x|)$, so
we need quantifiers like

For NP,... $C_{i,t}(<x_{i,t}>)^m \Rightarrow C_{j,t}(<y_{j,t}>)$, we should add existential quantifiers on configurations. In general, ...

2. $\Sigma_3$:Probability Classes. For each formula, $\Psi$ we add $\Pr(\Psi) > \alpha$, $\Pr(\Psi) < \alpha$ to the set of formulas.

3. $\Sigma_4$:Interactive proofs. Quantifiers on machines and

Quantifiers on V, P and sentences like $V \leftrightarrow P$.

To check the truth of the following

TC + Existence of random generator $\mathcal{H} \varphi$ implies

TC + $\mathrm{CON}(\mathrm{TC}^*) \mathcal{H} \varphi$.

We should consider the language which $\varphi$ is defined in it.

...

...

**Generlization 2.**

Here, we try to answer the following question

Do the above theorems and conclusions remain true if we consider oracle Turing machines?

The major problem in this discussion, is the existence of random generator by considering oracle Turing machines. More exactly,

**Definition 15.** X-random generator is an oracle Turing machine with oracle X, which feeds by random seeds we have normal distribution as output.
**Definition 16.** A random generator is independent of oracle X, if it is a X-random generator.

A random generator is independent of oracle, if it is a X-random generator for any X.

(Random generator independent of oracle A).

**Theorem 7.** If there exists random generator independent of oracle X, $P^X \neq NP^X$.

**Proof.** Analogous to the above proof (relative version of it). □

**Corollary 6.** If $X \in \text{Pspace} - \text{Complete}$, we have no X-random generator. (As a theory in TC).

We use this result in the next chapter.

**5. Polynomial Hierarchy**

In this chapter, we try to generalize the previous results to the classes of polynomial hierarchy. Firstly, PSPACE* is defined similar to P*. In the next step, $\Sigma_n^*, \Pi_n^*$

$\Sigma_n^* - \text{Complete} \Pi_n^* - \text{Compelete, are defined similar to}$

$NP^*, \text{ Co} - NP^*, \text{ NP}^* - \text{Compelete, Co} - NP^* - \text{Compelete.}$

**Definition 17.** PSPACE* is a class of problems such that, for any p$\in$PSPACE* and the probability $\alpha$, we have a polynomial $Q_{\alpha,p}$ and an associated algorithm $A_{\alpha,p}$ to solve $p$ by probability $\alpha$ such that $Q_{\alpha,p}$ is upper bound of the computation space.

Equivalently, for any p$\in$PSPACE* ($p$ as a language) and probability $\alpha$ we have an associated algorithm $B_{\alpha,p}$ and a polynomial $Q_{\alpha,p}$ as an upper bound of the computation space.

$x \in p \rightarrow \text{By probability } \alpha, B_{\alpha,p} = 1$

$x \notin p \rightarrow \text{By probability } \alpha, B_{\alpha,p} = 0$
**Theorem 8.** $PSPACE^* = NSPACE^*$.

**Theorem 9.** $PSPACE^* \subset NSPACE^*$.

**Proof.** Let $X \in PSPACE^*$, so there is a fuzzy deterministic Turing Machine which solve this problem by using finite memory and decision takes place in bounded polynomial time. Equivalently, there exists a deterministic Turing Machine which its transitive closure solves this problem by using finite memory decision takes place, in bounded polynomial time. The transitive closure of this deterministic Turing Machine is a non-deterministic Turing Machine. Hence, $X \in PSPACE^*$. □

Analogous proof, shows $NSPACE^* \subset NSPACE^*$.

**Definition 18.** *Transitive closure of a deterministic Turing Machine with transition function $\delta$, is transitive closure of the following relation $\geq$*

$C_2 \succ C_1$ if $\delta(C_1) = C_2$ among configurations of this Turing Machine.

Similarly, we have the following definition

**Definition 19.** *Transitive closure of a deterministic Turing Machine with transition function $\delta$, is transitive closure of the following relation*

$C_2 \succsim C_1$ if $C_2 \in \delta(C_1)$ among configurations of this Turing Machine.

**Theorem 10.** $NSPACE^* \subset NSPACE^*$.

**Proof.** Let $X \in PSPACE^*$, so there is a fuzzy non-deterministic Turing Machine which solve this problem by using finite memory and decides, in bounded polynomial time. Equivalently, there exists a non-deterministic Turing Machine which its transitive closure solve this problem by using finite memory decides, in bounded polynomial time. The transitive closure of this non-deterministic Turing Machine is a non-deterministic Turing Machine, again. Hence, $X \in NPSPACE^*$. □

**Corollary 7.** $PSPACE \subset PSPACE^* \subset NSPACE^* \subset NSPACE$, by savitch theorem we have, $PSPACE = PSPACE^* = NSPACE^* = NSPACE^*$.

**Definition 20.** $X \in PSPACE^*$ – Complete, if

1. $X \in PSPACE^*$.
2. $\forall Y \in \text{PSPACE}^* \ X >_{m}^* Y$

**Theorem 11.** Every PSPACE – Compelete problem is a PSPACE* – Compelete problem. (Page 7)

**Proof.** Remind that, $Y >_{m} X$ implies $Y >_{m}^{*} X$. □

In below, we generalize the concepts and definitions in the previous chapter, first we define PH, PH*.

**Definition 21.**

$$\Sigma_0^P = \Delta_0^P = \Pi_0^P = P$$

$$\Delta_{i+1}^P = P^{\Sigma_i^P}$$

$$\Sigma_{i+1}^P = NP^{\Sigma_i^P},$$

$$\Pi_{i+1}^P = \text{Co} - NP^{\Sigma_i^P}$$

$$\text{PH} = \bigcup \Delta_k^P$$

$$P^{\Sigma_i^P}, NP^{\Sigma_i^P}, \text{Co} - NP^{\Sigma_i^P}.$$

**Definition 22.**

$$\Sigma_0^{P,*} = \Delta_0^{P,*} = \Pi_0^{P,*} = P^*$$

$$\Delta_{i+1}^{P,*} = P^{\Sigma_i^{P,*}}$$

$$\Sigma_{i+1}^{P,*} = NP^{\Sigma_i^{P,*}},$$

$$\Pi_{i+1}^{P,*} = \text{Co} - NP^{\Sigma_i^{P,*}}$$

$$\text{PH}^* = \bigcup \Delta_k^P.$$

**Definition 23.** sat$_n$ = {$\Phi$: ∃X$_1$ ∀X$_2$ ∃X$_3$ ... AX$_i \ \Phi = 1$}, A∈{∃, ∀} such that X$_1$, X$_2$, X$_3$, ... , X$_i$ is a partition of variables of $\Phi$.

**Theorem 12.** The existence of Random generator independent of oracle sat$_{i+1}$, implies $\Sigma_{i+1}^P \neq \Delta_{i+1}^P$.

**Proof.** Similar to the case $i = 0$, when we feed the generator algorithm with oracle sat$_{i+1}$ by the random seeds we have stream of random numbers. By choosing Non-deterministically (by using sat$_{i+1}$ oracle-non deterministic Turing machine) the seeds, we have all the given strings. Equivalently, the generator is in $\Sigma_{i+1}^P$.
If $\Sigma_{i+1}^P = \Delta_{i+1}^P$, the generator algorithm is in $\Delta_{i+1}^P$, so the generator is not pseudorandom. □

**Definition 24.** We call the existence of Random generator independent of oracle X, EX.

**Theorem 13.** $\Sigma_{i+1}^P = \Delta_{i+1}^P$ iff $\Sigma_{i+1}^{P,*} = \Delta_{i+1}^{P,*}$.

This is the result of Theorem 16 & 17 in below.

By considering the above definition and by fuzzifying time we defined NP*.

We define $\Sigma_i^{P,*}$ --hard, $\Sigma_i^{P,*}$ -Complete likewise in below

**Definition 25** X is $\Sigma_i^{P,*}$ --hard if for any $Y \in \Sigma_i^{P,*}$ --hard, $X >_{m}^{*} Y$.

**Definition 26** X is $\Sigma_i^{P,*}$ -Complete if X is $\Sigma_i^{P,*}$ --hard and $X \in \Sigma_i^{P,*}$ .

**Theorem 14** SAT$_i$ is $\Sigma_i^P$ -Complete.

**Theorem 15** SAT$_i$ is $\Sigma_i^{P,*}$ -Complete.

**Proof.** SAT$_i$ belongs to $\Sigma_i^P$, hence SAT$_i \in \Sigma_i^{P,*}$ , by definition. The analogous proof of Cook-Levin's theorem works here. More exactly, by employing the reduction associated with the above reduction function h in the above theorem, with this difference that time is fuzzy, we have the analogous function h* in the new proof, also here, we consider $>_{m}^{*}$ instead of m -reducibility. Lemma 3 guarantees the proof of the theorem. □

**Theorem 16.** $\Sigma_{i+1}^{P,*} \neq \Delta_{i+1}^{P,*}$ implies $\Sigma_{i+1}^{P} \neq \Delta_{i+1}^{P}$.

**Proof.** To prove $\Sigma_{i+1}^P \neq \Delta_{i+1}^P$, we apply Theorem 2 and lemma 3.
Suppose $\Sigma_{i+1}^P = \Delta_{i+1}^P$ and we remind that $SAT_{i+1}$ is a $\Sigma_{i+1}^P$-Complete problem.
Hence, there is an oracle Turing Machine $A^{SAT_i}$ which solves $SAT_{i+1}$ in Polynomial
time.

Considering Fuzzy time, $A^{SAT_i}$ also solves $SAT_{i+1}$ in polynomial time,
hence $SAT_{i+1}$ belongs to $\Delta_{i+1}^{P,*}$. $SAT_{i+1}$ is $\Sigma_{i+1}^P$-Complete, so $\Sigma_{i+1}^{P,*} = \Delta_{i+1}^{P,*}$, a
contradiction. Consequently, $\Sigma_{i+1}^P \neq \Delta_{i+1}^P$. $\square$

**Lemma 5.** $SAT_{i+1} \notin \Delta_{i+1}^P$ implies $SAT_{i+1} \notin \Delta_{i+1}^{P,*}$, unless $\Sigma_{i+1}^P = \Delta_{i+1}^P$.

**Proof.** $SAT_{i+1}$ is $\Sigma_{i+1}^{P,*}$-Complete. Suppose $SAT_{i+1} \notin \Delta_{i+1}^P$. If $SAT_{i+1} \in \Delta_{i+1}^{P,*}$ then
$\Sigma_{i+1}^{P,*} = \Delta_{i+1}^{P,*}$. In brief, $\Sigma_{i+1}^P \neq \Delta_{i+1}^P$ implies $\Sigma_{i+1}^{P,*} = \Delta_{i+1}^{P,*}$, which contradicts last
theorem. $\square$

**Theorem 17.** $\Sigma_{i+1}^P \neq \Delta_{i+1}^P$ implies $\Sigma_{i+1}^{P,*} \neq \Delta_{i+1}^{P,*}$.

**Proof.** Suppose $\Sigma_{i+1}^P \neq \Delta_{i+1}^P$. By above lemma, $\Sigma_{i+1}^P \neq \Delta_{i+1}^P$ implies $SAT_{i+1} \notin \Delta_{i+1}^{P,*}$. But $SAT_{i+1} \in \Sigma_{i+1}^{P,*}$, so $\Sigma_{i+1}^{P,*} \neq \Delta_{i+1}^{P,*}$. $\square$

Now, we have our major result in this section

**Remark 4.** Analogous to the previous chapter we have, $TC+CON(TC^*) + \forall i \in N$ $ESAT_i \notin \Sigma_{i+1}^P \neq \Delta_{i+1}^P$. So, under this assumption PH does not collapse.

**Theorem 18.** $TC + CON(TC^*) + \forall i \in N$ $ESAT_i \notin PH^* \subseteq NSPACE^*$.

**Proof.** Easy by above.

**Conjecture.** For any $i \in N$, there exists Random generator independent of oracle $SAT_i$, $ESAT_i$.

**Discussion.** Intuitively, the following hypothesis seems true,

“The random generator, made by fuzzy time is independent of oracle $X \in PH$”.
The author has no proof for that, but this hypothesis and above theorems
concludes $\mathbf{PH}^* \& \mathbf{PH}$ do not collapse. We call the above hypothesis $\mathbf{ftrg-hypothesis}$
(fuzzy time random generator hypothesis). Under this hypothesis we have

$P \not\subseteq NP \not\subseteq PH$ and $P \not\subseteq NP \not\subseteq PSPACE$
$(P^* \not\subseteq NP^* \not\subseteq PH^*$ and $P^* \not\subseteq NP^* \not\subseteq PSPACE^*$).

So, $\mathbf{PH} \not\subseteq \mathbf{PSPACE}$ a parallel proof shows, $\mathbf{PH}^* \not\subseteq \mathbf{PSPACE}^*$.

To do more exactly, we show, there exist $\mathbf{PSPACE}^* - \text{Complete}, \Sigma_n^{*} - \text{Complete}, \Pi_n^{*} - \text{Complete}$ problems. Actually, it is easy to prove them by theorems in [2].

**Proposition 7.** $X \in \mathbf{PSPACE} - \text{Complete}$ then $X \in \mathbf{PSPACE}^* - \text{Complete}$.

**Proposition 8.** $X \in \Sigma_n$ — Complete ($\Pi_n$ — Complete) then $X \in \Sigma_n^*$ — Complete ($\Pi_n^*$ — Complete).

**Remark 5.**, At first glance, the above conclusion seems to be theorems in TC but actually, we need $\text{CON}(\mathbf{TC}^*)$ and existence of a model for $\mathbf{TC}^*$ to prove it. It is noticeable that, our language is not first order. More exactly, we have

3. $\mathbf{TC} + \text{CON}(\mathbf{TC}^*) + \mathbf{ftrg} \vdash \mathbf{P}^* \neq \mathbf{NP}, \mathbf{P} \not\subseteq \mathbf{NP} \not\subseteq \mathbf{PH} \not\subseteq \mathbf{PSPACE}$
The second type of conclusions, needs $\mathbf{TC}^*$ as premises too,

2. $\mathbf{TC} + \text{CON}(\mathbf{TC}^*) + \mathbf{TC}^* + \mathbf{ftrg} \vdash \mathbf{P}^* \neq \mathbf{NP}^*, \mathbf{P}^* \not\subseteq \mathbf{NP}^* \not\subseteq \mathbf{PH}^* \not\subseteq \mathbf{PSPACE}^*$

In above, by $\text{CON}(T)$ we mean theory T is consistent and has a model.

As a corollary, $\mathbf{TC} + \text{CON}(\mathbf{TC}^*) + \mathbf{TC}^* + \mathbf{ftrg}$ deduces graph isomorphism is not a NP-Complete problem.

**6. Quantum Complexity Classes**

Here, we consider Fuzzy time particle interpretation of quantum mechanics [6], [7], [8] as a true theory and the basis for theory of Quantum Computation (we call this hypothesis f-hypothesis). Based on this hypothesis and novel interpretation, time is considered as a fuzzy concept. Under the above considerations, we have the following results, immediately by definition
1. $BQP = BQP^*, BQP^* = BPP^* = P^*$.

2. $QIP = QIP^*$.

3. $QMA^* = MA^* = AM^* = QAM^*(= QMA = QAM)$ (By employing theorem $(MA^* = AM^*)$).

**Results of 2.** We have $QIP = PSPACE$ [9], [10](The proof should be checked again in the new interpretation, unless f hypothesis considered a true hypothesis). By considering above, we have $PSPACE = PSPACE^*$. As a result we have, $IP = IP^*$.

**Results of 3.** Since $MA \subset QCMA \subset QMA$, we have $MA^* \subset QCMA^* \subset QMA^*$. By 3, we have, $MA^* = QCMA^* = QMA^*$.

**Results of 1&3.** By $TC + CON( TC^*)$ we have $P^* \neq NP^*(= MA^* = QCMA^* = QMA^*)$. As an important result, $BQP \neq QMA(= QAM = QCMA)$.

The above results are based on a Physical assumption; means different interpretations of quantum Mechanics give the same classes of computational Complexity. It is valuable trying to find some more exact Mathematical proofs.

To complete the above to have a Mathematical proof, we should prove and check the proofs of the below claims in the new interpretation:

$$QIP = PSPACE$$

$$MA \subset QCMA \subset QMA$$

If the above results are being refuted, our Physical assumption would be in danger! It seems unlikely.

**Note.** Seemingly in the proof of $QIP = PSPACE$ [9], [10] we employ superposition of the states in quantum mechanics and if we show how superposition of the states is depicted in this new interpretation, we have a similar proof as it exists in the article.

The explanation would be as following

In any fuzzy instant of time, we have a linear combination of different states. This instant can be depicted as function and the x axis of graph of this function, is
abstract time (similar to classical time). In any point of x-axis the system is in one of the states, so the system in this fuzzy instant of time is a combination of states.

We face a new question again: How we find the associated state to a point (abstract time) in x-axis for any fuzzy instant of time?

Although this question is a plausible question for our model, nevertheless it is not a physical question, since in this theory, abstract time is not a Physical concept.

**Comment 1.** The interesting article "Oracle separation of BQP and PH"

By Ran Raz, Avishey Tal [21], has a major impact on the results in this article.

Firstly, $BQP = BQP^* = BPP^* = P^*$ by above. Consequently, by [21],
$P^* \neq P$.

Second, BQP is a subset of PSPACE. So PSPACE is not equal PH.

Anyway, the sixth reason in introduction, governs here too.

**Comment 2.** If we replace Fuzzy time-particle interpretation with any other interpretation in which fuzzy time or probabilistic time is considered, we have the same results.

**Comment 3.** In general, this article is continuation of the author's thesis.

In brief, approximately between 1999-2010 a line of research takes shape in France, based on a logical approach for Complexity theory problems. In return, it was based on abstraction of a Computational Model (Blum-Shub-Smale Machine) [11],[12],[13].

Some other works of complexity theorists are closely related, which should be mentioned. In these works the Theory of Computation is investigated under changing Physical rules and Models [14], [15], [16], [22].

Also, working on P vs NSPACE problem, and unusual hardship of this

problem leads the author to the idea that probably something in foundation should be changed.

The author studies of Theory of Computation and Mathematical Logic returns back to the time he took courses in these field settings, and did some research in
Sharif university (Mathematics and Physics departments) and IPM, when some researchers and Professors from France, Iran, Russia (Kazan, Moscow, Novosibirsk) and USA visited there. Later, during 1998-1999, the author visited France, University Lyon 1. The author wrote his PhD thesis based on the ideas, discussions there and some topics in Computability Theory[20].

In continuation, when the author works as a professor in Amir kabir university, he tries to check a new Physical model, to provide a new approach and Theory, a logical-Physical approach. So he introduced and study *TC*\* (Theory of Fuzzy Time Computation).

The strategy and the starting idea is employing the strategy of proof in

Gödel theorem. So as a novel way, the author tries to use, a convenient paradox solving the Complexity Theory problems to play the similar role of the Liar paradox in Gödel Theorems. The chosen paradox is "Unexpected Hanging paradox". Indeed, firstly, with some modification in "Unexpected Hanging paradox", it is shown that we have a contradiction in the modified version, not only a paradox. Trying to solve this paradox leads the author to the idea of "Fuzzy Time", which is the basis for this research and theory of Fuzzy time computation. In this article, as the second part of investigation the author shows how this novel theory, impacts some major problems in Computational Complexity Theory. The first part provides the motivation to define fuzzy time, nevertheless we could consider the second part independent of the first.

In brief, here the paper and the author achievement and novelty is to employ the idea of fuzzy time in Theory of Computation along with checking and experimenting the other ways.

Some cites, Seminars & Conferences:

CV

https://philpeople.org/public_cashe/file?content_type=application%2Fpdf&key=ga029mu34v0xpwi4p0eqin82n249

https://www.ssrn.com/

https://www.geneology.math.ndsu.nodak.edu/id.php?id=13829

https://aut.ac.ir/cv/2125/FarzadDidehvar

1. When proof doesn't show the Truth, Philosophy Day in Iran (Logic and Philosophical Logic, Tradition and Modern), 2010/11/19, Tehran, Iran.

2. A Semantic Situation without Syntax (Non-axiomatizibility of Theories), Universal Logic 2015, (5th World Congress and school, 2015/6/28, Istanbul University).
3. Is Classical Mathematics Appropriate for Theory of Computation?, Universal Logic 2018, (6<sup>th</sup> World Congress and school, 2018/6/28, Vichy University Campus).

4. Fuzzy Time, from Paradox to Paradox, The 50<sup>th</sup> Annual Iranian Mathematics Conferences, Shiraz, Iran, Shiraz University, 26-29 August, 2019, Shiraz University.

5. The impacts of Logic, Paradoxes in on side and Theory of Computation in the other side (Fuzzy Time Computation), 20 June 2022 (In Persian), https://ialogic.ir/index.php/2022-12-11-17-07-09/lectures/258--2022-06--15--05-07-35
The slides are in Philpapers.

6. About a Proof (TC + CON(TC) ∨ (P≠NP)), The 10<sup>th</sup> Annual Conference of the Iranian Logic Association, February, 22, 2023- February, 23, 2023

## Refrences

1. L.Babai "TRADING Group Theory for Randomness", STOC'85: Proceedings of the seventeenth annual ACM symposium on Theory of Computing, ACM, pp.421-429, 1985

2. O.Goldreich, In a world of P=BPP, Studies in Complexity and Cryptography (Miscellanea on the interplay between Randomness and Computation pp 191-232, 2011, Springer

3. O.Goldreich, Studies in Complexity and Cryptography: Miscellanea on the interplay between Randomness and Computation, Vol 6650 of Lecture Notes in Computer Science, Springer 2011, P 43.

4. S.Goldwasser; M.Sipser "Private coins versus public coins in interactive proof systems", STOC'86: Proceedings of the eighteenth annual ACM symposium on Theory of Computing, ACM, PP.59-68, 1986

5. M. Van Aten, On Brouwer, Wadsworth Philosopher's Series, 2004

6. F.Didehvar, Computing Fuzzy Time Function, SSRN 2022

7. F.Didehvar, Does accepting Fuzzy time-Particle interpretation of Quantum Mechanics, Refute the other interpretation? (Is fuzziness of time checkable experimentally?), Philpapers, 2021/09/04.

8. F.Didehvar, Fuzzy time a solution for unexpected hanging Paradox (a Fuzzy interpretation Of Quntum Mechanics), Philpapers 2019-4-13

9. R.Jain, Z.Ji, S.Upadyay, J.Watrus, QIP=PSPACE, arxiv: 0907.4737, 27 July 2009

10. R.Jain, Z.Ji, S.Upadyay, J.Watrus, QIP=PSPACE, Journal of the ACM, Volume 58, Issue 6, NO:30, pp 1-27

11. L. Blum, F.Cucker, M.Shub, S. Smale, Complexity and Real Computation, Spinger, 1998

12. L. Blum, M.Shub, S. Smale, "On a Theory of Computation and Complexity over the real numbers: NP-Comleness, Recursive Functions and Universal Machines, Bull.Amer.Mth.Soc.(N.S.) 21 (1): 1-46 (July 1989).

13. B.Poizat, Les petit cailloux. Une approach modele-theorique de l'Algorithmie, Nur al-Mantiq wal-Ma'rifah, no.3.Ale'as, Lyon 1995, 2 pp.
Under changing Physical rules and models, Aranson's work

14. S.Aaranson, Guest Column: NP-Completeness problem and physical reality ACM Sigact News, 36(1), 30-52, 2005

15. S.Aaranson, Bavarian. M, Gueltrini. G, Compuabilitiy theory of closed time like curves, arXiv preprint arXiv: 1609.05507, 2016

16. S.Aaranson, J.Wattrous, Closed timelike curves make quantum and classical computing equivalent, Proceedings of the Royal Society: Mathematical, Physical and Engineering Sciences, 465, 631-647, 2012. (?)

17. F. Didehvar, Theory of Fuzzy Time Computation(TC*), Philpapers, ssrn2023

18. F. Didehvar, Theory of Fuzzy Time Computation (2), (TC + CON(TC*)HP ≠ NP)
F.Didehvar, Philpapers, ssrn2023

19. F. Didehvar, Theory of Fuzzy Time Computation (3), (TC + CON(TC*)HP ≠ NP)
F.Didehvar, Philpapers, ssrn2023

20. F. Didehvar, Some Concepts and Problems in Theory of Complexity in Structures, published as "Generalization of Some Concepts Theory in Structures", Ph.D Thesis, 2002.

21. R.Raz, A.Tal, "Oracle separation of BQP and PH", Journal of
The ACM, Volume69, Issue 4, 2022.

22. S. Babaee, F.Didehvar, Turing Machines Equiped with CTC Physical Universe,
arxiv:2301.11632, 2023