-1

Concerning an NP problem, such as the travelling salesmen problem.

Say for a graph with N nodes there exists an algorithm $A(N)$ which can solve the problem in time $N^3$ (for example).

But.... to find each algorithm $A(N)$ takes $2^N$ steps. However, once you have an algorithm $A(N)$ you can solve any graph with $N$ nodes in $N^3$ steps.

So my question is, is this P or NP? Since in practical terms if you found the algorithm for graphs with 100 nodes $A(100)$, you could solve all graphs in time $100^3$.

Or is it somewhere in between?

Obviously the algorithm for finding algorithms $A(N)$ is NP. But the set of algorithms once found $A(N)$ works in P.

Edit: Because it is unclear

Consider a computer program called A(10) which can solve the travelling salesman problem for 10 nodes in $10^3$ steps.

Now consider another unrelated computer program A(11) which can solve the travelling salesman problem for 11 nodes in $11^3$ steps.

Another third completely different computer program A(12) which can solve the travelling salesman problem for 12 nodes in $12^3$ steps.

Consider a computer program B (a meta program) which can construct different computer programs A(N). Program B takes $2^N$ time to construct the simplest computer program to solve the case of N nodes.

Running program B can generate different computer programs A(1), A(2), A(3),... for all the different numbers of nodes.

Perhaps it can be proven that program B can create programs A(N) that run in $N^3$ steps. Hence a travelling salesman visits lots of countries and always visits 100 cities. Using the program B he generates an algorithm A(100) that runs in $100^3$ steps. This is very useful even though no general algorithm exists.

Asaf Karagila
  • 393,674
zooby
  • 4,343
  • There's a constant time program for all graphs of 100 (or fewer) nodes. It's just an impossibly large list of every single case. The point of any complexity theory like this is an algorithm that works for arbitrarily large graphs. – Mark S. Nov 09 '15 at 17:23
  • Yes but checking every single case is not polynomial in terms of the number of nodes $A(N)>2^N$. My point is it may be possible to prove that for any N it is possible to find an algorithm A(N) in non-polynomial time that can solve any graph with nodes N in less than N^a steps for some a (once you have the algorithm). But no general polynomial algorithm may exist. – zooby Nov 09 '15 at 17:33
  • You don't start with $N$, first of all. The point is to let $N$ vary. You have to pick $A$ first and find out how $A$ solves problems of size $N$ to even give meaning to "polynomial time in $N$." So your second sentence is flawed. We don't pick the graph first, then the algorithm - each individual graph has a constant-time solution - you just output the right number. – Thomas Andrews Nov 09 '15 at 17:37
  • Very unclear question. What do you mean by "to find each algorithm $A(N)$ takes $2^N$ steps" ??? –  Nov 09 '15 at 17:37
  • 1
    The question appears to be asking: suppose there is an algorithm that has two stages. The first stage takes $2^N$ steps, and the second takes $N^3$ steps. However the first stage is the same for all problems of size $N$. Hence if we wanted to solve a single problem, it takes $2^N+N^3$ steps. If we wanted to solve $M$ problems, all the same size, it takes $2^N+MN^3$ steps. – vadim123 Nov 09 '15 at 17:41
  • 3
    NP doesn't mean non-polynomial ! –  Nov 09 '15 at 17:46
  • @ vadim123 But the point is you would only have to do the first step once $2^N$. And then you could solve all programs of size N nodes in $N^3$ time. You might even just guess the first step, or read it out of a history book written 2000 years ago, so it would take no time at all. – zooby Nov 09 '15 at 17:51
  • @Thomas Andrews My sentence wasn't flawed. I meant exactly what I was saying. – zooby Nov 09 '15 at 17:59
  • 1
    Don't get defensive, you came here asking help. Yes, it is flawed. You are being very imprecise. – Thomas Andrews Nov 09 '15 at 18:01
  • @Thomas I think maybe we are crossing wires. While the sentence is not flawed, the method of generating a polynomial time algorithm I described is flawed in so far as the definition of polynomial time algorithms go. I am being defensive because to say the sentence is flawed suggests it doesn't mean what I wrote it to mean. Maybe I'm being pedantic. But you have to be very precise when dealing with logic. "two is an odd number" is not a flawed sentence but it is a flawed conclusion of the axioms of arithmetic. – zooby Nov 09 '15 at 18:11
  • No, it means nothing to give an algorithm after finding $N$. Once $N$ is fixed, there is no such thing as an algorithm in polynomial time in $N$. It is meaningless. Polynomial time in $N$ means for all $N$, and your statement implies it just involves a single $N$ (and an algorithm chosen after $N$ is chosen.) – Thomas Andrews Nov 09 '15 at 18:13
  • If you read the question I didn't say that. I said an algorithm A(N) that takes $N^3$ steps. I deliberately didn't use the word polynomial time. Thus algorithm A(5) would take 125 steps. Algorithm A(6) would take 216 steps. Never, mind, I can see you are failing to engage with the question. – zooby Nov 09 '15 at 18:17
  • "you would only have to do the first step once $2^N$. And then you could solve all programs of size $N$ nodes in $N^3$ time": this is where the flaw lies. You can't do that for all $N$. –  Nov 09 '15 at 18:53

1 Answers1

1

If every $N$ requires to run a procedure that "builds" an algorithm in time $2^N$, then to execute the algorithm in time $N^3$, the complete task has exponential complexity.

You may not assume that the algorithm for any $N$ is available at no cost, as this would require infinite precomputation and storage.

Note that this discussion has nothing to do with the NP class of problems.

  • OK. I'll take this as the answer. But I wonder if there is a special name for a problem that can be solved in P by first constructing an algorithm take exponential time? It would still be very useful thing to do. For example if you constructed an algorithm that could factor any 100 digit number in polynomial time but no others. You could still crack open a lot of safes. – zooby Nov 09 '15 at 17:56
  • That would be a perfectly useless thing. Exponential algorithms are restricted to tiny values of $N$. –  Nov 09 '15 at 18:24
  • Not necessarily. What above $1.001^N$ ? – zooby Nov 09 '15 at 18:28
  • 1
    Yep, that's a perfect example. For $N=100000$, a tiny value, you get $2\cdot10^{43}$, far beyond the lifetime of the universe using all computers on Earth. –  Nov 09 '15 at 18:47