np or np complete proof of a factory problem

Question

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,

Answer 1

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$

Answer 2

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