6
$\begingroup$

Let $P$ - polynomial($P(x) \ge x$), $n \in \mathbb{N}$, $l < log(n)$.

Problem1: "Is there program with length $\le l$ that print $n$ by using $\le P(log(n))$ time?"

Is it Problem1 $\in NP$-complete?

Now I'll explain why I think that this problem hasn't a polynomial solution.

Define "Kolmogorov complexity with time" $K(P, n)$ as minimal program that work $\le P(log(n))$ time.

Kolmogorov complexity is not a computable function. A natural analogue of this statement:

"Kolmogorov complexity with time" $\notin P$ (1)

It is easy to see, that if Problem1 $\in P$ than "Kolmogorov complexity with time" $\in P$. So, if Problem1 $\in NP$-complete than (1) $\iff P \not=NP$

Improve this question
$\endgroup$
5
  • $\begingroup$ Could you clarify explicitly what is the input for problem 1? The way you write it currently, you seem to fix $n$ and $l$ before asking the problem, and so it isn't clear what is the input. $\endgroup$
    – Joel David Hamkins
    Commented Sep 21, 2013 at 15:26
  • 1
    $\begingroup$ As I understand it, $P$ is fixed, $n, \ell$ are parameters. The phrase before the problem gives just the range of $n,\ell$. What should also be fixed is a model of computation, say, a concrete type of Turing machines. Otherwise the problem does not make sense. $\endgroup$
    – user6976
    Commented Sep 21, 2013 at 16:01
  • $\begingroup$ Mark, I agree, that seems to be the only sensible interpretation. In this case, it is in NP, since one can guess the program, and then check if it works. $\endgroup$
    – Joel David Hamkins
    Commented Sep 21, 2013 at 16:14
  • 1
    $\begingroup$ Alexey, I don't think that your template for proving $P\neq NP$ will work, because the strategy seems to relativize to oracles, but we know that $P^A=NP^A$ is possible for some oracles, by a result of Solovay. $\endgroup$
    – Joel David Hamkins
    Commented Sep 21, 2013 at 16:24
  • $\begingroup$ Mark, Yes, you are right. $\endgroup$
    – Alexey Milovanov
    Commented Sep 21, 2013 at 17:18

1 Answer 1

Reset to default
5
$\begingroup$

Let's assume that Mark's description of the problem in the comments is correct, so that we have a fixed polynomial $P$, and the decision problem is: given $l$ and $n$, such that $l\lt \log(n)$, decide if there is some program $e$ with length $\leq l$ such that $e$ prints $n$ using time $\leq P(\log(n))$.

This problem is in NP, because we can simply guess the program that works and check that it works in polynomial time. Note that since $n$ is an input, for NP here we are guided by polynomial time in the length of $n$. For the NP algorithm, on input $(l,n,e)$, we verify whether $e$ is a successful candidate or not, simply checking the length requirement and then running $e$ for $P(\log(n))$ steps to see whether it writes $n$ or not. If it does, we accept, and otherwise reject. The point is that this verification process is polynomial time in our input $(l,n)$. The input $(l,n)$ is acceptable in your problem if and only if there is a successful candidate $e$ making it acceptable in my algorithm, and this shows that your problem is in NP.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm sorry I wanted to ask: Is it Problem1 ∈NP-complete? $\endgroup$
    – Alexey Milovanov
    Commented Sep 21, 2013 at 17:15
  • $\begingroup$ Since we are guessing only less than $\log n$ bits of $e$, doesn't this proof show that the problem is, in fact, in P? Moreover, we could even test whether the program runs in time $P(n)$. $\endgroup$
    – Jan Kyncl
    Commented Jan 22, 2014 at 19:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .