3
$\begingroup$

Good evening everyone;

I face with this problem and I could not find a way to proof it. Here is the problem;

A={Writing out the factorial of a number in unary NP-complete or NP-hard (e.g. n! = 11 for n= 2)}

The thing that I don't understand is this problem should be in A ∈P.I assume we can write a function on polynomial time to solve this problem? Should we assume that P=NP and give a function in a programming language that does this in order to proof?

Regards,

$\endgroup$
  • $\begingroup$ How many digits do you expect for a number $n$? $\endgroup$ – miniBill Dec 27 '13 at 21:44
  • $\begingroup$ n can be all positive integers. $\endgroup$ – Can Dec 27 '13 at 21:47
  • $\begingroup$ Sorry, I meant: how many digits of output do you expect for a number $n$. $\endgroup$ – miniBill Dec 27 '13 at 21:49
  • $\begingroup$ Dear minibill; There is no limitations about number of digits of an output. if n=5 5!=120 so I expect 111111...(120) ones. $\endgroup$ – Can Dec 27 '13 at 21:53
  • $\begingroup$ It was an hint in the right direction :) Let me write an answer. $\endgroup$ – miniBill Dec 27 '13 at 21:54
1
$\begingroup$

There's some conceptual trouble from the outset, in that the P and (in particular) NP classes are usually only defined for decision problems -- that is, problems where there is only two possible answers to every instance of the problem. The task of outputting $n!$ symbols is not of this kind, and therefore it doesn't make much sense to ask whether it is in NP.

The usual way to apply the P/NP question to such a problem is to reformulate it as a family of decision problems -- for example,

Given $n$ and $k$, what is the $k$th bit of the binary representation of $n!$, counting from the ones end?

The complexity class can, however, also depend on the input representation. In the above reformulation, if $n$ and $k$ are given in unary notation, then the problem is easily seen to be in $P$. But if they are given in binary notation, then it's not obvious to me that it is even in $NP$.

$\endgroup$
0
$\begingroup$

To write the factorial in unary you'll need to output $n!$ ones, and this will take time at least $n!$, which is not $O(n^k)$ for any $k \in N$

$\endgroup$
  • $\begingroup$ Dear minibill; Thanks for the answer. You are right it will take n!(!).I beg your pardon for my question but now this problem is NP complete,NP hard or NP? $\endgroup$ – Can Dec 27 '13 at 22:01
  • $\begingroup$ I think it's NP but neither complete nor hard, but I don't know how to prove it $\endgroup$ – miniBill Dec 27 '13 at 22:02
  • $\begingroup$ Thus, another question is lets say this is NP. Should we try to solve this problem in polynomial time? or there is certainly no way to solve this problem in polynomial time ? or there is way but we don't know yet ? $\endgroup$ – Can Dec 27 '13 at 22:10
  • $\begingroup$ Wait a sec... this problem is not in NP! I just noticed it $\endgroup$ – miniBill Dec 27 '13 at 22:14
  • $\begingroup$ That is really confusing. If you think P=NP yeah it is not but if you say P < NP how can I discriminate it is NP, NP completeness or NP-Hard ? $\endgroup$ – Can Dec 27 '13 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.