Farzad Didehvar
email: didehvar@aut.ac.ir

Amir Kabir

Keywords: ., P=BPP, Fuzzy Time, Probabilistic Time, TC*, Reducibility, Complexity Theory Problems

.

Throughout this article we show the positive impact of this change on Theory of Computation and Complexity Theory to rebuild it in a more successful and fruitful approach. We call this novel Theory TC*.

Introduction

Here, we try to build the structure of a Theory of computation based on considering time as a fuzzy concept.

Actually, there are some reasons to consider time as a fuzzy concept. In this article, we don't go to this side but we remind that Brower and Husserl ideas about the concept of time were similar [START_REF] Van Aten | Wadsworth Philosopher's Series[END_REF].

Throughout this article, we present the Theory of Computation with Fuzzy Time. Considering the classical definition of Turing Machine we change and modify the concept of Time to Fuzzy time. We call this new Theory TC* [START_REF] Didehvar | Fuzzy Time & NP Hardness (P*=BPP*, P* NP*[END_REF] 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 are solved [START_REF] Didehvar | Fuzzy Time & NP Hardness (P*=BPP*, P* NP*[END_REF]. It should be mentioned that in this article, we consider fuzzy number a symmetric one. The point about the symmetry is in the proof of Lemma 3, although we are able to generalize it.

More specifically, we define the new classes of complexity Theory, P*, NP*, BPP* in TC* analogues to the definitions P, NP, BPP as their natural substituted definition. We show P* NP*, P*= BPP*. Finally, we have Theorem 4.

Reducibility

In this section, first we define a quasi order relation in TC* analogues to m-reducibility in TC.

We should remind that a fuzzy time Turing Machine is a Turing Machine which works in fuzzy time.

In addition, our Turing Machine is a two tuple (M,S). M is a Turing machine in the usual sense and s is a polynomial function, here M runs in bounded time S equivalently in this machine we compute M(x) in less than S([x]) steps.

First we repeat the Classical definition of m-reducibility:

, if there is a polynomial time computable function f such that: Associated definition in TC* Definition 1 : For , if there is a polynomial time computable* function f such that:

1.

Pr (

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

By bounded time, we mean for function f there exists a Polynomial function h such that in less than h(length(x)).

We represent by a 5-tuple, , is the number of steps that f(x) is computed. We define it as follows is an acceptable 5-tuple Is this definition independent from the value of α? ( In the first step in order to answer the above question, we need the following simple lemma from probability.

Lemma 1. Let for

, is an acceptable 5-tuple then for any there is a computable function in which is a 5-tuple.

Proof. Actually there is k, such that g= (k times repeating f till we reach a solution with probability . It is easy to see that, there is such a k.

Definition 2. Lemma 1, shows for , is independent from . So, we write .

Lemma 2.

is a quasi order.

Proof. implies (*) implies (**)

From (*), (**) we have (***).

Lemma 3. implies

Proof. Here, we consider the fuzzy number is symmetric.

We have computable function f such that f is supported by . The computation of f on x can be depicted by the following transition of configurations in time to reach the final configuration. Now, we change time to be fuzzy as it is mentioned in above. Now the probability of reaching or passing the final configuration is more than the probability of not to reach to this point.

By probability rules and above comment, if we consummate 2 unit of time, the probability of reaching to the final configuration or passing it, is more than and the probability of not to reach to this final configuration is less than . Likewise by consumption of p unit of time, the probability of reaching to the final configuration or passing it, is more than and the probability of not to reach to this final configuration is less than . So we have, Remark 1. By lemma 3, suppose we have a computation by Turing Machine and input x and classical time. If we change the classical time to symmetric fuzzy time the probability we reach to final state is more than As a conclusion, If we consider for computation the probability to reach final state is more than .

P*, NP*, NP*-hard, NP*-Compelete

One of the major question here is how we define the most important classes in Complexity Theory in the new theory? As a start we try to define P*. As the first attempt, we try to define it as following: P* is the class of all problems that are decidable by a Fuzzy Turing Machine (M,S).

But what do we mean by decidable, exactly? Since it is possible we do not reach to final state, So we should speak about the possibility of xϵp for any pϵP* when x belongs to p , and the possibility of x/ϵp when x belongs to . Hence by above consideration we define P* as following:

Definition 3: P* is the class of problems for any pϵ P* and probability α we have a polynomial , and an associated algorithm , for solving p by probability α such that , is upper bound of time of computation. Equivalently, for any pϵ P* (p as a language) and probability α we have an associated algorithm , and a polynomial , as an upper bound of time of computation xϵp → By probability , ,( )=1 x/ϵp → By probability , , ( )=0 This is equivalent to the definition of the class BPP. Additionally, by considering time as a Fuzzy concept we have BPP*. It is easy to see that it defines the same class as BPP. Consequently Theorem 1 P*=BPP*(=BPP) [START_REF] Didehvar | By considering Fuzzy time, P=BPP (P*=BPP*)[END_REF], [START_REF] Didehvar | Fuzzy Time & NP Hardness (P*=BPP*, P* NP*[END_REF].

The next natural question in TC* is the situation of the problem P vs NP, more exactly P* vs NP*.

Proposition 1 Random Generator exists [START_REF] Didehvar | By considering Fuzzy time, P=BPP (P*=BPP*)[END_REF], [START_REF] Didehvar | Fuzzy Time & NP Hardness (P*=BPP*, P* NP*[END_REF].

Proof. By inventing an algorithm we show that random generator exists. It is sufficient to consider an algorithm 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 seen easily that we have a random number generator. More exactly, by considering fuzzy time we have probability function p(x),

. Such that for any X+t, and n is a natural number If X is an odd number by probability p(t) in X+t is equal to 1 ( p(t) is near to 1) If X is an even number by probability p(t) in X+t is equal to 0 ( p(t) is near to 1)

The diagram of p(t). It is periodic.

First 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 are deterministic polynomial time Turing machine and , such that for every input x with length ( = )

1. belongs to D implies there exists string z with length such that for all string y with length )

2. belongs to D implies for all string z with length such that for all string y with length (The definition is Quoted [START_REF] Goldwasser | Private coins versus public coins in interactive proof systems[END_REF])

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

We define NP*-hard, NP*-Complete likewise in below Definition 5 is NP*-hard if for any *, .

Definition 6 X is NP*-Complete if X is NP*-hard and *.
Theorem 2 SAT is NP*-Complete.

Proof. SAT belongs to NP, hence *, by definition.

Analogues to the proof of Cook-Levin theorem by repeating it, and considering the associated reduction by function f when time is fuzzy we have the same function f and considering instead of m-reducibility. Lemma 3 guarantees the proof of theorem.

In [START_REF] Didehvar | Fuzzy time, A Solution of Unexpected Hanging Paradox[END_REF], by defining the concepts P, BPP in the new framework we have t is shown that the new classes , are both equivalent to BPP. In contrast, what about the substitution of class of NP in this new framework. To represent NP problems in the Theory of Algorithm, it is required to define a new class for that. Possibly the best choice in probabilistic classes in this purpose is MA [START_REF] Babai | TRADING Group Theory for Randomness[END_REF], [START_REF] Goldwasser | Private coins versus public coins in interactive proof systems[END_REF] (introduced by Laszlo Babai, Shafi Goldwasser, Micheal Sipser).

The complexity class MA is known as the candidate of NP problems in probabilistic classes, also we have a theorem states [12] This point besides strengthen our choice. So, we try to define the NP concept in fuzzy time by applying the definition of MA.

Here, we define MA in Two sided version definition [START_REF] Goldwasser | Private coins versus public coins in interactive proof systems[END_REF]. The two last questions remained unproved.

It is easy to see:

1.

2.

(Considering certificate definition of NP) 3.

Chapter 2.Pseudorandom generator &

Pseudo random generators play a major role in Theory of computation. The existence of pseudo random generator by applying classical time leads us to P≠NP. What about theory of computation when we consider time as a fuzzy concept ( ?

By proposition 1, more strongly, we have random generator in our Theory, To obtain our main result in Theorem*, we define NP+.

Definition 7

 7 The Complexity class MA is the set of decision problems like D such that there are deterministic polynomial time Turing machine and , such that for every input x with length ( = ) 3. belongs to D implies there exists string z with length such that for all string y with length ) 4. belongs to D implies for all string z with length such that for all string y with length (The definition is Quoted [13]) As a conclusion, by changing and transforming the literature of Theory of Computation from Classical Time to Fuzzy time the classes of Complexity Theory changes to new classes. Likewise, We have new problems. The list of new possible classes are and Instead of problem we have the following problems

To prove , we apply Theorem 2 and lemma 3.

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

By considering Fuzzy time, A solves SAT in polynomial time too and SAT belongs to P*. SAT is NP*-Complete, so P*=NP*. A contradiction.

Consequently,

Conclusion.

Here, we show considering time as a fuzzy concept, have some major results in solving some famous problems in Complexity Theory in a way that it adopts to the intuition and expectations of people in Theory of Algorithm. In brief, P*≠NP*, P*=BPP*. Finally we prove P≠NP.