Frank Vega

SEQUENCES OF LANGUAGES WHEN THE LIMIT GOES TO INFINITY

Keywords: 2000 Mathematics Subject Classification. Primary 68Q15, Secondary 11A07, 11A51 P, NP, UP, NP-complete, Quadratic Congruences, Subset Product. 1

This work is specifically about an interesting class of problems called the NP-complete problems, whose status is unknown. No polynomialtime algorithm has yet been discovered for some NP-complete problem. If any single NP-complete problem can be solved in polynomial-time, then every NP problem has a polynomial-time algorithm. We study two new complexity classes which have a close relation to the NP-complete problems. We call these classes as infinite-UP and infinite-P. Informally, the class infinite-UP contains those languages that are the limit of a sequence of languages in UP when this sequence goes to infinity. The class infinite-P is similar but the languages in the sequence are in P. In addition, in those sequences every previous language is a strict subset of the next one. We show two NP-complete problems which are infinite-UP and infinite-P respectively. In this way, we demonstrate some new properties of the NP-complete problems which can help us to understand better the P versus NP problem.

Introduction

P versus N P is a major unsolved problem in computer science [START_REF] Fortnow | The Golden Ticket: P, NP, and the Search for the Impossible[END_REF]. This problem was introduced in 1971 by Stephen Cook [START_REF] Arora | Computational complexity: A modern approach[END_REF]. It is considered by many to be the most important open problem in the field [START_REF] Fortnow | The Golden Ticket: P, NP, and the Search for the Impossible[END_REF]. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution [START_REF] Fortnow | The Golden Ticket: P, NP, and the Search for the Impossible[END_REF].

In 1936, Turing developed his theoretical computational model [START_REF] Arora | Computational complexity: A modern approach[END_REF]. The deterministic and nondeterministic Turing machines have become in two of the most important definitions related to this theoretical model for computation. A deterministic Turing machine has only one next action for each step defined in its program or transition function [START_REF] Papadimitriou | Computational Complexity[END_REF]. A nondeterministic Turing machine could contain more than one action defined for each step of its program, where this one is no longer a function, but a relation [START_REF] Papadimitriou | Computational Complexity[END_REF].

Another huge advance in the last century has been the definition of a complexity class. A language over an alphabet is any set of strings made up of symbols from that alphabet [START_REF] Thomas | Introduction to Algorithms[END_REF]. A complexity class is a set of problems, which are represented as a language, grouped by measures such as the running time, memory, etc [START_REF] Thomas | Introduction to Algorithms[END_REF].

In the computational complexity theory, the class P contains those languages that can be decided in polynomial time by a deterministic Turing machine [START_REF] Goldreich | Np-Completeness[END_REF]. The class N P consists in those languages that can be decided in polynomial time by a nondeterministic Turing machine [START_REF] Goldreich | Np-Completeness[END_REF].

The biggest open question in theoretical computer science concerns the relationship between these classes: Is P equal to N P ? In 2002, a poll of 100 researchers showed that 61 believed that the answer was not, 9 believed that the answer was yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and so impossible to prove or disprove [START_REF] William | The P=?NP poll[END_REF]. All efforts to solve the P versus N P problem have failed [START_REF] Papadimitriou | Computational Complexity[END_REF].

Another major complexity class is U P . The class U P has all the languages that are decided in polynomial time by a nondeterministic Turing machines with at most one accepting computation for each input [START_REF] Valiant | Relative Complexity of Checking and Evaluating[END_REF]. It is obvious that P ⊆ U P ⊆ N P [START_REF] Papadimitriou | Computational Complexity[END_REF]. Whether P = U P is another fundamental question that it is as important as it is unresolved [START_REF] Papadimitriou | Computational Complexity[END_REF]. All efforts to solve the P versus U P problem have failed [START_REF] Papadimitriou | Computational Complexity[END_REF].

We consider two new complexity classes that are called infinite-UP and infinite-P which have a close relation to the NP-complete problems. We define a problem that we call General Quadratic Congruences. We show General Quadratic Congruences is an NP-complete problem. Moreover, we prove General Quadratic Congruences is also in infinite-UP. In addition, we define another problem that we call Simple Subset Product. We show Simple Subset Product is an NP-complete problem. Furthermore, we prove Simple Subset Product is also in infinite-P.

Theoretical notions

Let Σ be a finite alphabet with at least two elements, and let Σ * be the set of finite strings over Σ [START_REF] Arora | Computational complexity: A modern approach[END_REF]. A Turing machine M has an associated input alphabet Σ [START_REF] Arora | Computational complexity: A modern approach[END_REF]. For each string w in Σ * there is a computation associated with M on input w [START_REF] Arora | Computational complexity: A modern approach[END_REF]. We say that M accepts w if this computation terminates in the accepting state, that is, M (w) = "yes" [START_REF] Arora | Computational complexity: A modern approach[END_REF]. Note that M fails to accept w either if this computation ends in the rejecting state, or if the computation fails to terminate [START_REF] Arora | Computational complexity: A modern approach[END_REF].

The language accepted by a Turing machine M , denoted L(M ), has an associated alphabet Σ and is defined by

L(M ) = {w ∈ Σ * : M (w) = "yes"}.
We denote by t M (w) the number of steps in the computation of M on input w [START_REF] Arora | Computational complexity: A modern approach[END_REF].

For n ∈ N we denote by T M (n) the worst case run time of M ; that is

T M (n) = max{t M (w) : w ∈ Σ n }
where Σ n is the set of all strings over Σ of length n [START_REF] Arora | Computational complexity: A modern approach[END_REF]. We say that M runs in polynomial time if there exists k such that for all n, T M (n

) ≤ n k + k [1]. Definition 1.1. A language L is in class P if L = L(M )
for some deterministic Turing machine M which runs in polynomial time [START_REF] Arora | Computational complexity: A modern approach[END_REF].

We state the complexity class N P using the following definition. Definition 1.2. A verifier for a language L is a deterministic Turing machine M , where L = {w : M (w, c) = "yes" for some string c}.

We measure the time of a verifier only in terms of the length of w, so a polynomial time verifier runs in polynomial time in the length of w [START_REF] Sipser | Introduction to the Theory of Computation[END_REF]. A verifier uses additional information, represented by the symbol c, to verify that a string w is a member of L. This information is called certificate.

Observe that, for polynomial time verifiers, the certificate is polynomially bounded by the length of w, because that is all the verifier can access in its time bound [START_REF] Sipser | Introduction to the Theory of Computation[END_REF]. Definition 1.3. N P is the class of languages that have polynomial time verifiers [START_REF] Sipser | Introduction to the Theory of Computation[END_REF].

In addition, we can define another complexity class called U P . Definition 1.4. A language L is in U P if every instance of L with a given certificate can be verified by a polynomial time verifier, and this verifier machine only accepts at most one certificate for each problem instance [START_REF] Hemaspaandra | Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets[END_REF]. More formally, a language L belongs to U P if there exists a polynomial time verifier M and a constant c such that if x ∈ L, then there exists a unique certificate y with |y| = O(|x| c ) such that M (x, y) = "yes", if x / ∈ L, there is no certificate y with |y| = O(|x| c ) such that M (x, y) = "yes" [START_REF] Hemaspaandra | Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets[END_REF].

A function f : Σ * → Σ * is a polynomial time computable function if some deterministic Turing machine M , on every input w, halts in polynomial time with just f (w) on its tape [START_REF] Sipser | Introduction to the Theory of Computation[END_REF]. Let {0, 1} * be the infinite set of binary strings, we say that a language

L 1 ⊆ {0, 1} * is polynomial time reducible to a language L 2 ⊆ {0, 1} * , written L 1 ≤ p L 2 , if there exists a polynomial time computable function f : {0, 1} * → {0, 1} * such that for all x ∈ {0, 1} * , x ∈ L 1 iff f (x) ∈ L 2
where iff means "if and only if". An important complexity class is NP-complete [START_REF] Goldreich | Np-Completeness[END_REF]. A language L ⊆ {0, 1} * is NP-complete if (1) L ∈ N P , and (2) L ≤ p L for every L ∈ N P . Furthermore, if L is a language such that L ≤ p L for some L ∈ NP-complete, then L is in NP-hard [START_REF] Thomas | Introduction to Algorithms[END_REF]. Moreover, if L ∈ N P , then L ∈ NP-complete [START_REF] Thomas | Introduction to Algorithms[END_REF]. If any single NP-complete problem can be solved in polynomial time, then every N P problem has a polynomial time algorithm [START_REF] Thomas | Introduction to Algorithms[END_REF]. No polynomial time algorithm has yet been discovered for any NP-complete problem [START_REF] Fortnow | The Golden Ticket: P, NP, and the Search for the Impossible[END_REF].

A principal NP-complete problem is SAT [START_REF] Goldreich | Np-Completeness[END_REF]. An instance of SAT is a Boolean formula φ which is composed of (1) Boolean variables: x 1 , x 2 , . . . , x n ;

(2) Boolean connectives: Any Boolean function with one or two inputs and one output, such as ∧(AND), ∨(OR), (NOT), ⇒(implication), ⇔(iff); (3) and parentheses.

A truth assignment for a Boolean formula φ is a set of values for the variables in φ. A satisfying truth assignment is a truth assignment that causes φ to be evaluated as true. A formula with a satisfying truth assignment is a satisfiable formula. The problem SAT asks whether a given Boolean formula is satisfiable [START_REF] Goldreich | Np-Completeness[END_REF].

Another NP-complete language is 3CN F satisfiability, or 3SAT [START_REF] Thomas | Introduction to Algorithms[END_REF]. We define 3CN F satisfiability using the following terms. A literal in a Boolean formula is an occurrence of a variable or its negation [START_REF] Thomas | Introduction to Algorithms[END_REF]. A Boolean formula is in conjunctive normal form, or CN F , if it is expressed as an AND of clauses, each of which is the OR of one or more literals [START_REF] Thomas | Introduction to Algorithms[END_REF]. A Boolean formula is in 3-conjunctive normal form or 3CN F , if each clause has exactly three distinct literals [START_REF] Thomas | Introduction to Algorithms[END_REF].

For example, the Boolean formula

(x 1 ∨ x 1 ∨ x 2 ) ∧ (x 3 ∨ x 2 ∨ x 4 ) ∧ ( x 1 ∨ x 3 ∨ x 4 )
is in 3CN F . The first of its three clauses is (x 1 ∨ x 1 ∨ x 2 ), which contains the three literals x 1 ,

x 1 , and x 2 . In 3SAT , it is asked whether a given Boolean formula φ in 3CN F is satisfiable.

It can be demonstrated that many problems belong to NP-complete using a polynomial time reduction from 3SAT [START_REF] Goldreich | Np-Completeness[END_REF]. For example, the well-known problem 1-IN-3 3SAT which is defined as follows: Given a Boolean formula φ in 3CN F , is there a truth assignment such that each clause in φ has exactly one true literal? 2. Results

infinite-UP.

Definition 2.1. We say that a language L belongs to U P ∞ if there exist an infinite sequence of languages L 1 , L 2 , L 3 . . . where for each i ∈ N every language L i is in U P , has an infinite cardinality, the set L i+1 -L i has infinite elements and

L i ⊂ L i+1 such that lim i→∞ L i = L.
We call the complexity class U P ∞ as "infinite-UP". Since QC ∈ NP-complete then GQC ∈ NP-complete.

The distinct prime factors of a positive integer n >= 2 are defined as the ω(n) numbers p 1 , . . . , p ω(n) in the prime factorization

n = p a1 1 × p a2 2 × . . . × p a ω(n)
ω(n) . Lemma 2.6. There will exist a constant α, such that there are infinite positive integers n which complies with ω(n) ≤ α × ln ln n.

Proof. The average order of ω(n) is ω(n) ∼ ln ln n [START_REF] Hardy | Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work[END_REF]. Consequently, it will exist the constant α. If the congruence x 2 ≡ i 2 ( mod b ) has a solution, that solution is necessarily a solution to each of the prime power congruences x 2 ≡ i 2 ( mod p ei i ) when p ei i divides b [START_REF] Nagell | Introduction to Number Theory[END_REF]. For any prime p r , a necessary condition for x 2 ≡ i 2 ( mod p er r ) to have a solution is for x 2 ≡ i 2 ( mod p r ) to have a solution (to see this, note that if x 2 -i 2 is divisible by p er r then it is certainly divisible by p r ). Now, suppose x 2 ≡ i 2 ( mod p er r ) where p er r is a prime power which divides b . Then x 2 -i 2 ≡ (x -i) × (x + i) ≡ 0( mod p er r ). Thus p er r divides the product (x -i) × (x + i) and so p r divides the product as well. If p r = 2 and p r divides (x -i) × (x + i), then this is because x ≡ i( mod p r ) since the sum and the subtraction of two integers is even when both are even or odd at the same time. If p r is an odd prime and divides both (x -i) and (x + i), then p r would divide both their sum and their difference, 2 × x and -2 × i. Since p r is an odd prime, p r does not divide 2 and so p r would divide both x and i which can be translated to x ≡ i( mod p r ). It follows that p r either divides (x -i) or (x + i) but not both. Since p r divides (x -i) × (x + i), it only divides one of (x -i) and (x + i). Therefore, either x ≡ i( mod p r ) or x ≡ -i( mod p r ).

In this way, we prove for every prime p r that divides b we will have either x ≡ i( mod p r ) or x ≡ -i( mod p r ). Conversely, if we find all the possible solutions to each of the prime congruences, then we can use the Chinese Remainder Theorem to produce a solution to the original problem, that is to find the value of i [START_REF] Thomas | Introduction to Algorithms[END_REF]. Since the Chinese Remainder Theorem can be solved in polynomial time O(ln β b), then the remaining order will depend on the computation of all possible solutions. Since we only have two possible choices for each prime factor, then the order will depend on O(2 ω(b ) ). Since ω(b ) ≤ ω(b) ≤ α × ln ln b, then the final order will be of O(ln QUESTION: Is there a positive integer x such that Q(a, b, c, d, x) = true?

β b × 2 α×ln ln b ) = O(ln β b × ln α b) = O(ln k b) for a constant k = β + α.
We denote this problem as SQC.

Theorem 2.9. SQC ∈ U P .

Proof. We show a polynomial time verifier, and this verifier machine only accepts at most one certificate for each problem instance of SQC [START_REF] Hemaspaandra | Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets[END_REF]. Given five positive integers a, b, c, d and x, we define the verifier machine M for SQC as follows: M (a,b,c,d,x) = "yes" [START_REF] Hemaspaandra | Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets[END_REF].

M (a, b, c, d, x) = "yes"iff x is the minimum such that Q(a
The constant e exists because SQC ∈ N P . We denote this problem as CQC i .

Theorem 2.11. For every positive integer i we have that CQC i ∈ U P .

Proof. For i = 1, then CQC 1 = SQC and thus CQC 1 ∈ U P . Suppose for some i = k, then CQC k ∈ U P . Let's prove CQC k+1 ∈ U P . We will take an arbitrary instance (a, b, c, d) and some prime number p > 2 which does not divide b. The prime p can be taken in polynomial time in relation to log 2 b. Certainly, this can be done choosing a candidate from 3 to log 2 2 b because ω(b) ≤ log 2 b and the n th prime number is approximately equal to n × ln n < n 2 [START_REF] Nagell | Introduction to Number Theory[END_REF]. Let's take the number q = p ln 2 b . Since the congruence property

d × x 2 ≡ a( mod b) complies with q × d × x 2 ≡ q × a( mod q × b) then Q(a, b, c, d, x) = true if and only if Q(q × a, q × b, c, q × d, x) = true. However, if the instance (a, b, c, d) ∈ CQC k+1 , then the instance (q×a, q×b, c, q× d) ∈ CQC k because ω(q × b) = ω(b) + 1 ≤ (k + 1) × α × ln ln b + 1. Since p > 2 then q = p ln 2 b > b ln b . Therefore k × α × ln ln(q × b) > k × α × ln ln b ln b and this complies for k > 1 with k × α × ln ln b ln b = k × α × ln(ln b × ln b) = k × α × ln ln 2 b = 2 × k × α × ln ln b > (k + 1) × α × ln ln b + 1 ≥ ω(q × b).
In this way, we can reduce in polynomial time CQC k+1 to CQC k , since the calculation of q will be polynomial in relation to ln b if we use the exponentiating by squaring [START_REF] Thomas | Introduction to Algorithms[END_REF]. Since U P is closed under reductions and CQC k ∈ U P , it follows that CQC k+1 ∈ U P . Hence, by mathematical induction we have proved CQC i ∈ U P for every positive integer i [9]. Theorem 2.12. GQC ∈ U P ∞ .

Proof. For every positive integer i the set CQC i contains infinite elements. Indeed, for some positive integer b there are infinite numbers n such that ω(b) = ω(n), because there are infinite prime numbers [START_REF] Nagell | Introduction to Number Theory[END_REF]. Certainly, CQC i ⊂ CQC i+1 and the sets CQC i+1 -CQC i have infinite elements. Moreover, we can assure that

lim i→∞ CQC i = GQC.
Hence, we can affirm GQC ∈ U P ∞ .

infinite-P.

Definition 2.13. We say that a language L belongs to P ∞ if there exist an infinite sequence of languages L 1 , L 2 , L 3 . . . where for each i ∈ N every language L i is in P , has an infinite cardinality, the set L i+1 -L i has infinite elements and

L i ⊂ L i+1 such that lim i→∞ L i = L.
We call the complexity class P ∞ as "infinite-P".

Definition 2.14. SIMPLE SUBSET PRODUCT INSTANCE: A list of numbers L and a positive integer k with its prime factorization, such that the prime factorization of k does not contain any prime power with exponent greater than 1.

QUESTION: Is there a subset of numbers from L whose product is k?

We denote this problem as SSP .

Theorem 2.15. SSP ∈ NP-complete.

Proof. Since SSP is only a restriction of problem Subset P roduct, then SSP ∈ N P [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Certainly, we can check whether the product of a subset of numbers from L is indeed k in polynomial time. We present a polynomial time reduction from 1-IN-3 3SAT to SSP . For a 3CN F formula φ with m clauses and n variables, we consider the sets S 1,t , S 1,f . . . S n,t , S n,f ⊆ {1, . . . , m} such that S i,t (resp., S i,f ) is the set of the indices of the clauses (of φ) that are satisfied by setting the i th variable to true (resp., false). That is, if the i th variable appears un-negated in the j th clause then j ∈ S i,t , whereas if the i th variable appears negated in the j th clause then j ∈ S i,f . Indeed, S i,t ∪ S i,f equals the set of clauses containing an occurrence of the i th variable, and the union of all these 2 × n sets equals {1, . . . , m}. Besides, we augment the universe with n additional elements and add the i th such element to both S i,t and S i,f . Thus, the reduction proceeds as follows:

(1) On input a 3CN F formula φ (with n variables and m clauses), the reduction computes the sets S 1,t , S 1,f . . . S n,t , S n,f such that S i,t (resp., S i,f ) is the set of the indices of the clauses in which the i th variable appears un-negated (resp., negated). (2) The reduction creates the sets S 1 . . . S 2×n , where i = 1 . . . n it holds that S 2×i-1 = S i,t ∪ {m + i} and S 2×i = S i,f ∪ {m + i}. (3) Establish a bijective mapping between the numbers {1, . . . , m + n} and the first m + n prime numbers. Replace the members inside of S 1 . . . S 2×n with the mapped primes. (4) For each set in S 1 . . . S 2×n multiply its members together, the resulting list of products is L for the SSP instance. Because prime numbers are used for the mapping in the previous step, the products are guaranteed to be equivalent iff the sets are equivalent by the unique factorization theorem [START_REF] Nagell | Introduction to Number Theory[END_REF]. (5) Multiply the first m+n primes p 1 , . . . , p m+n together, the resulting product is the value k for the SSP instance. Note that (L, k) is a yes-instance of SSP iff φ is a yes-instance of 1-IN-3 3SAT. Assume, on the one hand, that φ has the certificate τ 1 , . . . , τ n . Then, for every j ∈ {1, . . . , m} there exists an i ∈ {1, . . . , n} such that setting the i th variable to τ i , satisfies the j th clause. Since, k does not contain prime powers with exponent greater than 1 then we guaranteed that exactly one literal is true per each clause.

The transformation steps involves operations that are polynomial to the size of the input φ. The first m + n primes can be generated in time O(m + n) using the sieve of Eratosthenes and are guaranteed to fit into O((m + n) 2 × ln(m + n)) space by the prime number theorem [START_REF] Nagell | Introduction to Number Theory[END_REF]. Definition 2.16. COMPLEX SUBSET PRODUCT ON I-TH PRIME INSTANCE: A list of numbers L and a positive integer k with its prime factorization, such that the prime factorization of k does not contain any prime power with exponent greater than 1 and no prime factor is greater than the i th prime number.

QUESTION: Is there a subset of numbers from L whose product is k?

We denote this problem as CSP i .

Theorem 2.17. For every positive integer i we have that CSP i ∈ P .

Proof. CSP 1 ∈ P , since the target k will necessarily be equal to 2. Indeed, we would only need to check whether the list L contains the number 2. Assume for some natural number i, we have CSP i ∈ P . Let's prove CSP i+1 ∈ P . Suppose we have an instance (L, k) of CSP i+1 . If the target k does not contain the (i + 1) th prime number, then (L, k) ∈ CSP i iff (L, k) ∈ CSP i+1 . If the target k is equal to the (i + 1) th prime number, then we remove the number 2 from the list L and later we replace the occurrence of the number p i+1 by the prime 2 inside the list L and target k. The resulting instance (L , k ) complies with (L , k ) ∈ CSP i iff (L, k) ∈ CSP i+1 . Now, suppose the target k contains the prime factor p i+1 and another p j where obviously p j < p i+1 . First, we remove those integers in L which have a power factor of p i+1 or p j with exponent greater than 1. Thus we multiply each pair of numbers inside of L such that those number contains either p i+1 or p j but not both. Next, we add these new integers within the list L. After that, we remove those previous numbers that contains only the prime factor p i+1 or p j but not both. Finally, we replace the product p i+1 × p j by the prime p j in the factorization of the elements in the resulting list. We do exactly the same with the target k which as well contains the product p i+1 × p j as a factor number of its factorization. The resulting instance (L , k ) complies with (L , k ) ∈ CSP i iff (L, k) ∈ CSP i+1 . Certainly, if (L, k) ∈ CSP i+1 then every possible certificate of (L, k) contains a pair of numbers which has the corresponding prime factor p i+1 or p j or just one single number that contains both. Besides, in every possible reduction the instance (L , k ) is polynomially bounded by (L, k).

In this way, we can reduce in polynomial time CSP i+1 to CSP i . Since P is closed under reductions and CSP i ∈ P , it follows that CSP i+1 ∈ P . Hence, for every i ∈ N we have proved CSP i ∈ P by mathematical induction [START_REF] Nagell | Introduction to Number Theory[END_REF].

Definition 2 . 2 .

 22 Given five positive integers a, b ,c, d and x, the boolean function Q(a, b, c, d, x) is true if and only if x < c and d × x 2 ≡ a( mod b) [9]. Definition 2.3. QUADRATIC CONGRUENCES INSTANCE: Positive integers a, b and c, such that we have the prime factorization of b. QUESTION: Is there a positive integer x such that Q(a, b, c, 1, x) = true? We denote this problem as QC. QC ∈ NP-complete [4]. Let's define another problem. Definition 2.4. GENERAL QUADRATIC CONGRUENCES INSTANCE: Positive integers a, b, c and d, such that we have the prime factorization of b. QUESTION: Is there a positive integer x such that Q(a, b, c, d, x) = true? We denote this problem as GQC. Theorem 2.5. GQC ∈ NP-complete. Proof. Since we can check Q(a, b, c, d, x) = true in polynomial time, then GQC ∈ N P . Indeed, the certificate x will be polynomially bounded by any instance (a, b, c, d) when Q(a, b, c, d, x) = true because x < c. In addition, we can reduce every instance (a, b, c) of QC into an instance (a, b, c, 1) of GQC in polynomial time where (a, b, c) ∈ QC iff (a, b, c, 1) ∈ GQC.

Theorem 2 . 7 .

 27 Given four positive integers a, b, c and d, such that we have the prime factorization of b and ω(b) ≤ α × ln ln b, then we can check whether a positive integer x is the minimum that complies Q(a, b, c, d, x) = true in order O(ln k b) for a constant k. Proof. Suppose we have a positive integer i such that 0 < i < x and Q(a, b, c, d, i) = true. Hence, we will obtain d × x 2 ≡ d × i 2 ( mod b). Moreover, by a property of congruences we have x 2 ≡ i 2 ( mod b ) where b = b (d,b) and (d, b) is the greatest common divisor of d and b [9]. We can find (d, b) in polynomial time in relation to ln b just multiplying into a single number each maximum prime power p ei i that divides b when also p ei i divides d. This is possible because we have the prime factorization of b. We are going to assume b = 1, because in case of (d, b) = b then x should be necessarily equal to 1.

Definition 2 . 8 .

 28 SIMPLE QUADRATIC CONGRUENCES INSTANCE: Positive integers a, b, c and d, such that we have the prime factorization of b and ω(b) ≤ α × ln ln b.

  , b, c, d, x) = true. SQC belongs to U P because the verifier M can run in polynomial time as we proved in Theorem 2.7 and there will be a constant e such that if (a, b, c, d) ∈ SQC, then there is a unique certificate x with |x| = O(|(a, b, c, d)| e ) such that M (a, b, c, d, x) = "yes", if (a, b, c, d) / ∈ SQC, there is no certificate x with |x| = O(|(a, b, c, d)| e ) such that

Definition 2 . 10 .

 210 COMPLEX QUADRATIC CONGRUENCES ON I INSTANCE: Positive integers a, b, c and d, such that we have the prime factorization of b and ω(b) ≤ i × α × ln ln b for a positive integer i. QUESTION: Is there a positive integer x such that Q(a, b, c, d, x) = true?

Theorem 2.18. SSP ∈ P ∞ .

Proof. For every positive integer i the set CSP i contains infinite elements. Indeed, the list L could vary into an infinite ways even though the target could be the same. Certainly, CSP i ⊂ CSP i+1 and the sets CSP i+1 -CSP i have infinite elements. Since there are infinite prime numbers, we can assure that lim i→∞ CSP i = SSP.

Hence, we can affirm SSP ∈ P ∞ .


Catherine Miller
email: miller@mmsh.univ-aix.fr

LANGUAGE, IDENTITIES AND IDEOLOGIES : A NEW ERA FOR SUDAN ?

Introduction.

Conflicts about language issues and language planning in the Sudan have accompanied the Sudanese political life since the early 20 th century. Until the mid 1980s, these linguistic conflicts were mainly reflecting the South/North polarization (cf. The Rejaf Conference of 1927, The Addis Abeba Agreement of 1972). From the mid 1980s, and with the spread of the regional conflicts to many « Northern » Sudanese Areas (Darfur, South Kordofan, Ingessana, Eastern Sudan etc.), linguistic claims have progressively emerged as one of the aspects of the cultural diversity of the whole Sudan. Therefore since 1997 a number of constitutional and political decrees have reconsidered the status of the Sudanese languages (cf. the decree of 22th November1997) including the May 26 th 2004 Naivasha Peace Agreement (For an analysis of this agreement see the paper of Ashraf Abdullay in this panel) and the current amendment of the Sudanese Constitution. The Naivasha Agreement can be considered as an historical landmark in this respect. For the first time since Independence, all Sudanese vernaculars (and not only Southern Sudanese vernaculars, as it was the case in the previous Addis Abeba Agreement) are recognized as potential national languages. This political and official recognition is extremely important because it provides the legal bases for a multilingual linguistic policy. But we know that between the enactment of a law or a decree and its concrete implementation there is always a huge gap and a very long span of time. Respecting language plurality and implementing fair multilingual language planning are not easy tasks, even within economically wealthy countries. This is because language planning involves both symbolic and pragmatic aspects. Language is one of the main symbolic flag of collective identity but there are often huge discrepancies between the symbolic importance of a language for a given collective identity (nation, region, ethnic group etc.) and the very role of this language in the socio-economical life of the citizen. Moreover, despite good will, lack of economical means often hamper the implementation of a multilingual policy.

In Sudan, the last decade has witnessed a progressive shift from a dominant state discourse and an active state policy supporting a pro-Arabization policy to a new emerging discourse supporting (at least theoretically) a multilingual policy. This shift occurs in a world-wide context where linguistic rights tend to be more and more considered as one of the basic universal human rights. It occurs also in an African Horn-regional context where new political powers (like in the case of Ethiopia and Eritrea) tend to implement an ethno-regional linguistic policy, each region being associated with a dominant ethno-linguistic group.

Therefore while the new political context of Sudan can raise many hopes concerning linguistic rights and cultural equality, it can also lead to many disappointments and ideological adventures.

One of the urgent tasks is to assess the present language situation of the Sudan and to highlight its complexity and its main dynamics. This is the main objective of the language panel presented in this conference. In this paper, I would like to briefly address the following issues:

Which tools do we have to assess the main dynamics of the language situation in the Sudan? What are the main factors behind such dynamics? How far do linguistic categories match with ethnic categorization? Can language planing escape the trap of linguistic nationalism and linguistic ideology?

I Sociolinguistic dynamics : Trends and Tools

Studies concerning languages in the Sudan can briefly be categorized in two main fields:

One is dedicated to the linguistic description of a number of Sudanese languages and eventually the classification of these languages within broader language families. This kind of studies have resulted in the publication of a number of books and articles concerning various Sudanese languages (no updated bibliography). It contributes to our knowledge of the Sudanese cultural and linguistic heritage but yet a lot remains to be done in this domain (see the papers of Vanhove, Quint, Jakobi in this panel). It often tells little about the actual status of these languages, some being endangered. It may be noted that most of the serious linguistic descriptive works have been done by Africanists (Foreigners or Sudanese) on African Sudanese languages and far less on the various varieties of Sudanese Arabic, whose most accurate descriptions remain unpublished PhD theses on Khartoum Arabic (to the notable exception of Reichmuth 1983 on Shukriyya Arabic and a number of publication on Juba Arabic).

The second field concerns the sociolinguistic status of the Sudanese languages and tries to analyses the main dynamics of language change, language maintenance and language death. Since the early 1970s, a number of language surveys have been undertaken in the Sudan, mostly under the umbrella of the IAAS, using quantitative and questionnaire-based methods [START_REF] Bell | Language Survey Questionnaire Manual[END_REF]. Starting from Jernud's preliminary study (1979), several volumes have been published under the supervision of Herman Bell (1979Bell ( -1981) ) as well as many unpublished MA and PhD (see some enclosed references). Most of these language surveys provide detailed data on language uses (Mother tongue, first language, degree of multilingualism, languages uses inside and outside home, across generations etc.). However the questionnaire have mainly been distributed to school students and rarely to ordinary citizen. They may therefore over evaluate the shift to Arabic. The questionnaire method raises some additional methodological concerns which will be discussed below.

Briefly speaking, almost all language surveys undertaken in the Sudan have pointed out to the increasing dominance and spread of Arabic as the main lingua franca or even first language (or mother tongue = MT) not only among the non-Arab migrant population of the northern cities like Khartoum (Miller & Abu Manga 1992, Mugaddim 2002) but also among the non Arab population of Darfur (Doornbos 1984, Salih 1989, Jahallah 2001+ an unpublished survey undertaken under the supervision of U. Mahmud in the late 1970s-early 1980s ), and the Nuba Mountain (Bell ed. 1979, Salih & Rothman 1988[START_REF] Jahallah | Al-Awdaa' Al-Lughawii Fii Madinat Al-Fashir (Language Uses in El Fashir Town)[END_REF], the Southern Blue Nile or in the main urban centers of Southern Sudan like Juba (Mahmud 1982), Dem Zubeir (Mahmud 1978),Wao or Malakal (as recorded until 1984, after this date no study on Southern Sudan has been available due to the war).

The spread of Arabic in Sudan is an old story, which still needs additional historical researches concerning the respective role of Islamization, trade roads, establishment of Muslim kingdoms, settlement of Arabic speaking groups, etc. (The spread of Arabic has been too systematically associated with Islamization, there are evidences that Arabization has been a slower process than usually described). During the colonial period, the spread of Arabic was not halted in spite of the British policy in Southern Sudan and the Nuba mountains between 1930 and 1946 (see [START_REF] Beshir | Educational Development in the Sudan, 1898 to 1956[END_REF], Hurreiz and Bell eds. 1975, Hurreiz and Abdel Salam eds 1989, Mahmoud 1983[START_REF] Sanderson | Education, Religion and Politics in Southern Sudan 1899-1964[END_REF]. The Arabization trend increased after Independence and seems to have considerably speed up in the last three decades due to the combination of several factors including urbanization, migration, mobility, schooling, pro-Arabization state policy, media etc. Among all these factors, we can say that socio-economic factors have been more influent in the spread of spoken colloquial Arabic than political and educational factors which foster the spread of Modern standard Arabic.

The spread of Arabic is also recorded in the data provided by two national censuses (1956 and 1993). The data of the 1956's census have been analyzed by a number of linguists (more particularly [START_REF] Thelwall | The Linguistic Settlement of the Nuba mountains[END_REF] and are still mainly referred to when people are looking for statistics on language and ethnicity. The ethno-linguistic data of the 1993's census, (which includes data on the Northern Sudan only but uses the same ethnic and language categories than the 1956's census) have, so far, not been widely circulated and I would like to thank my colleague François Ireton from the Cedej (Cairo), who provided me with a copy of the Census' tables and helped me in the computerization of the data.

The data of the censuses and the language surveys highlight the following phenomena:

1. The increasing discrepancy between ethnic affiliation and ethnic mother tongue, at least in Northern Sudan. This can be seen in the 1993's census (see table 1) and has been reported in all the studies of the language Survey, particularly among the young generations (see Mugadim's paper in this panel also) This difference according to ethnic group and region is due to a number of factors such as older processes of Arabization, higher mobility (urbanization and migration),very high linguistic diversity, lower demographic weight, etc. But the factors behind language maintenance and shift deserve further careful investigation. A recent studies on El Fashir [START_REF] Jahallah | Al-Awdaa' Al-Lughawii Fii Madinat Al-Fashir (Language Uses in El Fashir Town)[END_REF] indicates for example than the members of the Zaghawa ethnic groups appear far more resistant than all other ethnic groups, in spite of being a minority group in this city.

In urban context, ethnic clustering can help language maintenance as it is the case for the Haussa community of Dem Bakor in Gedarif town.

3. The linguistic impact of migration and urbanization cannot be summarized to language shift in favor of Arabic only. If the "Sudanisation process" (i.e. dominance of the Northern Riverain Urban culture in most Northern urban centers) described by Doornbos in the 1980s is still taking place, it is also clear that increasing language and cultural diversity characterize now the Northern Sudanese urban centers. In areas like Central Sudan and Khartoum, which were almost 90%-100% Arabic speaking in 1956, the massive population movement of the last two decades has led to an increasing ethnic and language diversity, as can be seen in table 4. Therefore the linear picture of a language shift towards Arabization, which emerges from most language survey has to be qualified. If it is certainly true that youngsters speak more and more Arabic compared to the older generation, it is also true that many Sudanese urban centers are now characterized by the coexistence of various languages. These languages are not only spoken within the households but can be spoken in public space (particularly market place) and start to be more and more present in the cultural arena (cf. the numerous musical tapes in various Sudanese languages which start to be widely circulated including songs in Dinka). To take again the example of Gedaref town, one can hear the common use of Hausa in the crop market and can buy commercial tapes of local urban songs in Tigre, Tigrinya, Hausa, etc.

II Language shift, language contact and ethnic affiliation

The data collected through questionnaire (censuses or language surveys) are important because they provide quantitative data which help to assess the degree of language change. But they also have to be taken with a lot of caution for many reasons. One concerns the reliability of the data collection, particularly concerning the 1993's census, where it is not sure that the questions pertaining to language have been always asked in a proper manner. The second is that there is always a discrepancy between what people pretend to speak and what they really speak. The third one is that questionnaires handle each language as a distinct category and tend to emphasize language boundaries without taking into account the fluidity of languages uses, which precisely characterizes language changes. An emblematic case of such a categorization is the use of the term Arabic as opposed to all other Sudanese Vernacular languages. By using a single label which encompasses a high degree of varieties going from Classical Arabic, Modern standard Arabic, Khartoum Arabic, the various regional Arabic, Juba Arabic, etc. the questionnaire method implicitly postulates the unity and uniqueness of Arabic vis à vis other languages. And this is a serious methodological bias.

Most studies on language uses in the Sudan tell us little about what type of Arabic is spoken by the people who claim to speak it as a first language: how far do non-Arab groups in the Nuba Mountains or in Darfur speak (or not) a specific Arabic variety compared to the neighbored Arab groups or to Khartoum Arabic ? What is the influence of their own language? How far do they wish to reproduce or not the norms of Khartoum Arabic? How far do they code switched, etc. etc. These are some of the many unanswered questions for the time being. The term "Arabic Mother Tongue" can refers to such distinct Arabic varieties that it would be misleading to think that it necessarily provides the people with a sense of a shared common language and moreover with a sense of a shared common culture. The case of Juba Arabic is the most typical counter example of such a false unity. It shows that an Arabicbased language can develop as a specific regional language, and has little to do structurally and culturally with MSA or Khartoum Arabic. Juba Arabic is now recognized as one of the linguistic expression of a Southern identity and it is sometimes used in theatrical stages or radio broadcast to express a Southern identity shared by people of various ethnic groups [START_REF] Miller | Juba Arabic as a way of expressing a Southern Sudanese Identity in Khartoum[END_REF]. It would be completely misleading to assume that the use of Juba Arabic as a mother tongue by a growing numbers of Southerners urban dwellers can be compared with the use of standard Sudanese Arabic. Therefore the process of language shift to Arabic (i.e. Arabization) can refer to very distinct linguistic dynamics and there is now an urgent need for developing a new trend of sociolinguist studies in Sudan, which will include more qualitative data and illustrate better the real language uses of the people and the degree of language mixing, complementing the information provided by the surveys.

One of the most interesting aspects of the Sudanese situation is the fact that language shift does not lead to the weakening of ethnic affiliation. On the opposite, the spread of Arabic have occurred at the same time than an increasing ethnic consciousness [START_REF] Miller | Linguistic policies and Language Issues in the Middle East[END_REF] and might have help the formation of supra-ethnic group solidarity like in the case of the Nuba (Abu Manga and Miller 1995). The few studies which have included questions on both languages uses and languages attitudes have indicated a strong maintenance of ethnic affiliation in spite of language change (Miller & Abu Manga 1992, Mugaddim 2002). Many people continue to have a positive attitude towards their language even if they speak it less and less. This point is certainly at the heart of a new trend toward a new linguistic consciousness. While Arab nationalism has based its moto on "Being an Arab is to speak Arabic", this does not apply to Sudan, where many people do speak Arabic as a fist language without considering themselves as Arabs. Many people reject Arabism when it is used to convey a sense of political supremacy based on racial heredity (see the numerous discourse of the SPLM about the status of Arabic). The Sudanese case illustrates how the linguistic nationalism have been a fiction. Language itself is not a sufficient tool of assimilation. Speaking Arabic does not make you an Arab if you belong to an ethnic group consider as non -Arab (the same process occurs in a country like France, where the fact of speaking French is not enough to make the migrants of the second-generation).

The time is now ready to drop out a number of ideological postulates which have been dominating not only the Sudanese political life but also a large part of the international research on language and identity. One is that the use of a supposed common language help to unify people. The second is the underlying presuppose that members of a common ethnic group necessarily share the same ethnic languages.

III. Language change and Linguistic nationalism

For decades, many Sudanese politicians and ideologists, influenced by an Arab linguistic nationalism have thought that imposing one common language (Arabic) to the whole Sudanese population will foster national integration and assimilation to a common core Arab culture. The political failure of such a language ideology is now obvious (Mahmud 1984[START_REF] Miller | Linguistic policies and Language Issues in the Middle East[END_REF], Yokwe 1997), although this policy succeeded in the public marginalization of all other Sudanese languages and the weakening of English. There has been a large debate to decide whether or not such a policy was due to the influence of political Islamism in the Sudanese political life (Abdul Salam 1989, Yokwe 1997). Although the association of Islamization and Arabization have play an important role in the Sudanese political life, particularly regarding Southern Sudan, it must be remembered that linguistic nationalism have been the creed of most modern states including the more secular one such as Turkey [START_REF] Miller | Linguistic policies and Language Issues in the Middle East[END_REF]. The pro-Arabization policy that dominated most of the Sudanese politics since Independence has to be understood as a reaction to the former colonial policy of divide and rules. A similar counter -reaction might dominated the analyses and the decisions of a number of new political forces in the Sudan. After five decades of Arabism, it is normal that a number of people and political associations wish to reverse the trend and break away with Arabic, which is associated with a particular political, cultural, racial and social domination One of the danger of such a counter reaction is the fact that these parties might fail in the same linguistic nationalist trap than their opponents by associating too closely a language with a specific culture or ethnic group, by denying the historical contact between Arabic and the local languages, by insisting that all members of their ethnic group share the same cultural values, etc. If the real linguistic and cultural diversity of the Sudan is to be recognized, this implies that a number of categories are abolished or at least not taken for granted. It means that instead of considering languages as separate and often conflictual entities, it must be understood that identity and cultural affiliation can be expressed in a diversity of voices, that the former "colonial languages" can be self appropriated. It means also that pragmatism prevails on purely ideological stands and that although all languages are equal "in nature", they are not "equal" on a socio-economic market and not all can play the same role. I am conscious that this is easy to say and extremely difficult to do, particularly after such a long conflict and such a long despise of vernacular cultures. A real new language planning will need difficult choices.

Conclusion

The language changes of the last decades must not be either over estimated nor under estimated. One of the main impact of such language shift is the clear discrepancy between claimed ethnic affiliation and claimed mother tongue. This means that the traditional ethnolinguistic categories, which have been established in the late 19 th -early 20 th centuries by the Colonial Anthropology and Administration have to be seriously questioned and cannot be taken as fix and immutable categories.

This language shift raises also serious dilemma for the associations acting for a defense and revalorization of their vernacular languages (see Eida Eissa in this panel). Can some endangered languages become something else than a folkloric heritage? How can the ordinary people be motivated by the defense of their vernaculars if they themselves already speak another one? Which are the languages which can play an educational role? How make a choice without creating new competition? I would like to conclude by saying that for the time being, it seems that most political parties do not seriously take into consideration the language issue. They limit themselves to "politically correct" declarations that will assure the respect of plurality without devoting any time, any expertise and any means on how such linguistic plurality can be institutionalized. The real competition is seen between English and Arabic, and this was also the case after the implementation of the Addis Abeba Agreement in 1972. The teaching of a selected numbers of Southern Languages remained largely theoretical for both financial and man-power reasons. Today it seems to me that the "defense" of the vernacular languages is largely let to a few and often penniless associations or individual will, while the task is enormous. In a way, (and I know that I am here rather provocative), this is maybe a rather good thing that the fate of the Sudanese languages is not too seriously dealt with by the politicians. It will maybe leave the space for more pragmatism and also maybe for a more creative approach.

Ce qu'il faudra que j'ajoute pendant la conférence c'est a) parler des décisions prises par le SPLA pour enseignement de l'anglais dans les Nuba Mountains depuis 2001 b) parler des radios-télévisions développé par UN c) dire que les chiffres du recensements sont beaucoup plus bas que ceux des languages surveys

Table 1 :

 1 Ethnic Affiliation and Mother Tongue in Northern Sudan according to the 1993's census

		Arab	Nuba	Beja	Nubiyi	Darfuri	West A South	Funj	Foreign	Not
					n		an		Sud		ers	Stated
	Ethnicity	51,79	4,71	6,41	3,22	22,12	7,42	1.74	1,31	0,77	0,50
	language	73,84	2,49	4,55	0,94	9,99	5,22	1.59	0,74	0,21	0,43
		(Note : the Census' categories have been clustered in major ethnic and language
		groups)
	2. The shift to Arabic varies according to region and ethnic groups. If we compare between
	claimed ethnicity and claimed language uses in what can be considered the home-land of
	each major ethnic group, we notice that the Nubiyins (in the Northern S.), the Nuba (in
	South Kordofan) and the Darfurian speaking groups (in Darfur) appear more affected by
	language shift to Arabic than the Beja in Eastern Sudan and the West Africans in most
	regions (table 2 and 3).
			Table 2 Distribution of major ethnic groups by Northern States
	State	Arabs Beja	Nubiyin Nuba Funj	Southerners Darfurian West African Foreigners Not stated
	Northern	44,07 0,98	46,66	4,50	0,01	2,34	1,05	0,04		0,12	0,22

Table 3

 3 Distribution of major language groups by Northern States

	State	Arabic Beja Nubiyi	Nuba Funj Southern Darfurian West African Foreigners Not stated
				n
	Northern	76,81	0,01	17,74 3,35	0,00	1,88	0,08	0,01	0,00	0,00
	Nahr al Nil	97,44	0,56	0,48	0,78	0,11	0,26	0,12	0,09	0,01	0,01
	Red Sea	25,91	63,77 1,60	2,83	0,01	1,00	0,42	3,24	0,80	0,05
	Kassala	30,67	43,93 3,65	1,44	0,04	0,72	7,92	10,27	0,82	0,04
	Gedarif	63,98	5,22	0,27	1,98	0,02	0,82	8,50	18,12	0,61	0,01
	Khartoum	85,44	0,17	1,02	3,97	0,02	4,46	2,00	1,69	0,41	0,09
	Gezira	93,80	0,06	0,06	0,50	0,00	0,31	1,79	3,15	0,06	0,00
	Sennar	75,48	0,04	0,03	0,85	0,02	1,11	2,81	19,38	0,03	0,00
	White Nile	90,03	0,01	0,11	1,06	0,00	1,94	1,23	5,35	0,01	0,01
	Blue Nile	40,38	0,10	0,13	3,09	29,36 3,39	2,61	20,34	0,04	0,00
	Northern K. 95,82	0,02	0,02	0,43	0,00	0,36	0,04	3,15	0,00	0,00
	Western K. 90,60	0,00	0,01	0,22	0,00	3,25	3,12	2,28	0,00	0,00
	Southern K. 64,71	0,03	0,86	23,13 0,01	0,75	0,49	9,86	0,01	0,03
	Northern D. 66,89	0,00	0,09	0,04	0,01	0,89	31,68	0,17	0,00	0,00
	Western D. 22,86	0,57	0,01	0,19	0,00	0,22	72,64	2,24	0,11	0,00
	Southern D. 76,66	0,06	0,00	0,45	0,00	1,07	18,13	3,24	0,00	0,00
	Total	73,84	4,55	0,94	2,49	0,74	1,59	9,99	5,22	0,19	0,02

Table 4 .

 4 Language distribution in Central Sudan according to the 1956 and 1993 National

	Censuses