Yioop - PHP Search Engine

Apr 20 In-Class Exercise Thread.

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

Best,

Chris

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

-- Apr 20 In-Class Exercise Thread

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.

(Edited: 2022-04-20)

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.

-- Apr 20 In-Class Exercise Thread

 
 
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

(Edited: 2022-04-20)

<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>

-- Apr 20 In-Class Exercise Thread

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

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

-- Apr 20 In-Class Exercise Thread

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> 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>

-- Apr 20 In-Class Exercise Thread

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.

-- Apr 20 In-Class Exercise Thread

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 == 0} is in P COMPOSITE = { | 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.

(Edited: 2022-04-20)

<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>

-- Apr 20 In-Class Exercise Thread

 
 
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(∣∣x∣∣c) 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> 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(∣∣x∣∣c) 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>

-- Apr 20 In-Class Exercise Thread

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.

-- Apr 20 In-Class Exercise Thread

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.

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}

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

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|)

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(i*j), and log_2(k) = O(log+2(i*j))

COMPOSITE is in NP.

(Edited: 2022-04-21)

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(i*j), and log_2(k) = O(log+2(i*j)) COMPOSITE is in NP.