Consider the following brute-force algorithm for solving the composite number pr

Question

Consider the following brute-force algorithm for solving the composite number problem: Check successive integers from 2 to ?n/2? as possible divisors of n. If one of them divides n evenly, return yes (i.e., the number is composite); if none of them does, return no. Why does this algorithm not put the problem in class P ?

-- Why is this problem not in P? Wouldn't you just iterate through the elements 2 through ?n/2? and check if each one divides n? That would make its upper bound complexity linear and therefore make it a problem that can be solved in polynomial time.

Explanation / Answer

ANS:-

Given that,

P is the class of decision problems for which we can find a solution in polynomial time.

Definition A polynomial time function is just a function that can be computed in a time polynomial in the size of its parameters.
Definition P is the class of decision problems (languages) L such that there is a polynomial time function f(x) where x is a string and f(x)=True (ie. yes) if and only if x is in L.
NP is the class of decision problems for which we can check solutions in polynomial time.
Definition NP is the class of decision problems (languages) L such that there is a polynomial time function f(x,c) where x is a string, c is another string whose size is polynomial in the size of x, and f(x,c)=True if and only if x is in L.
c in the definition is called a "certificate", the extra information needed to show that x is indeed in the language. NP stands for "nondeterministic polynomial time", from an alternate, but equivalent, definition involving nondeterministic Turing machines that are allowed to guess a certificate and then check it in polynomial time. (Note: A common error when speaking of P and NP is to misremember that NP stands for "non-polynomial"; avoid this trap, unless you want to prove it :-)
An example of a decision problem in NP is:

Decision Problem. Composite Number
Instance. Binary encoding of a positive integer n.
Language. All instances for which n is composite, i.e., not a prime number.

We can look at this as a language L by simply coding n in log n bits as a binary number, so every binary composite number is in L, and nothing else. We can show this problem is in NP by providing a polynomial time f(x,c) (also known as a "polynomial time proof system" for L). In this case, c can be the binary encoding of a non-trivial factor of n. Since c can be no bigger than n, the size of c is polynomial (at most linear) in the size of n. The function f simply checks to see whether c divides n evenly; if it does, then n is proved to be composite and f returns True. Since division can be done in time polynomial in the size of the operands, Composite Number is in NP.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.