Please post your solutions to the Apr 20 In-Class Exercise to this thread.

Best,

Chris

It can be proved to be in NP if the verification could be solved in polynomial time. We can check if n is composite by passing n and x as inputs to an algorithm A which checks if n%x==0 and division has a time complexity of n(length of binary n) which is polynomial making to be in p, resulting in COMPOSITE belonging to NP.

<pre>

Let A be the algorithm that checks whether a natural number is divisible by any number less than it.

An algorithm is polynomial because iterating would require o(n) steps and division is polynomial time. Hence we can say algorithm A is polynomial time.

We can write the language -

L={x{0,1}:y,|y|=O(|x|^c) and A(x,y)=1}

where x is encoding of natural number

</pre>

L ={ <n,x> | n%x == 0} We need to argue that there is a way to check, if x divides n evenly in time <= (|x| + |n|)^c for some fixed value c

<pre> Each composite number (n) is the product of two other numbers => consider every pair of natural numbers (x,y) where 1<x<=root(n) and 1<y<=n Checking if the product of each pair (x*y) == n is a problem that takes O(|x|+|y|)^k time (polynomial time) This makes the given problem a composite NP problem </pre>

To prove COMPOSITE is in NP, we need to prove that the verification for COMPOSITE can be done in polynomial time. We rewrite COMPOSITE = {<n> | <n, x> L} and L = {<n, x> | n % x == 0}. The algorithm used in L takes O(n) time where n is the length of the number in binary using the grade-school algorithm. Therefore, L is in P, and COMPOSITE is in NP.

<nowiki>

The language L belongs to the complexity class P if there exists an algorithm A such that A(x) accepts for the language L Otherwise A(x) rejects for the language L.

where X runs in polynomial time, ie, O(|X|^k)

We are trying to prove that: L = {<n, x> | n%x == 0} is in P

COMPOSITE = {<x, n> | <x, n> belongs to L}

A composite number represented as a binary string can be divided by another number within polynomial time using the grade school division algorithm. Since, at each iteration we process a single digit further in the number x, it is about quadratic in time.

This means that COMPOSITE belongs to P.

Which implies COMPOSITE belongs to NP. </nowiki>

<pre>

A language L belongs to NP if there exists a two input polynomial-time algorithm A and a constant c such that L={x{0,1}:y,y=O(xc) and A(x,y)=1}

L = {<n, x> | n % x == 0} for composite numbers to belong in P

As division can be done in polynomial time, so L belongs to P and hence NP.

</pre>

L= {<n, x> | n% x ==0} for composite numbers to belong in P. The values n and x can be passed to the algorithm to check if n%x==0. If the algorithm takes polynomial time to do the division(where n is the length of number in binary), then it is said to be in P and hence COMPOSITE is in NP.

To show COMPOSITE is in NP, an algorithm that determines if a number is composite and runs in polynomial time to the input bits should be provided. <pre> Let an algorithm A that takes [[i, j], k] accepts if k = i × j and rejects all other cases.

COMPOSITE = { k | ∃ A([i, j], k) accepts} </pre>

• multiplication can be done in polynomial time to the input length.

<pre> By using long multiplication, i × j can be calculated: Step 1: multiply each binary digit of j to i (if the binary digit of j is 0 => 0, if the binary digit of j is 1 => i) => O(|j|) Step 2: we get |j| many products to add up for the final result => O(|j|) </pre> So the time complexity for A is O(|j|), which is polynomial to the input length.

• length of k is log_2(k) and length of [i, j] is log_2(ij), and log_2(k) = O(log+2(ij))

COMPOSITE is in NP.