Is it possible to solve a problem of O(n!) complexity within a reasonable time given infinite number of processing units and infinite space?
The typical example of O(n!) problem is brute-force search: trying all permutations (ordered combinations).
A:
Disregarding the cost of setup (whatever that might be...assigning a range of values to a processing unit, for instance), then yes. In such a case, any value less than infinity could be solved in one concurrent iteration across an equal number of processing units.
Setup, however, is something significant to disregard.
Adam Robinson
2010-03-29 16:47:16
Why any value less than infinity? Given an infinite number of processors, shouldn't they be able to handle an equal number (infinite) of processes? Infinity hurts my brain sometimes
Bob
2010-03-29 16:49:34
@Bob: Because every value is less than infinity ;)
Adam Robinson
2010-03-29 16:56:55
No because it takes an infinite time to distribute a job to infinite machines - it also takes a really long time to open the boxes and install them.
Martin Beckett
2010-03-29 16:59:05
@Martin: That's why I said "disregarding the cost of setup".
Adam Robinson
2010-03-29 17:01:57
+6
A:
It sure is. Consider the Traveling Salesman Problem in it's strict NP form: given this list of costs for traveling from each point to each other point, can you put together a tour with cost less than K? With the new infinite-core CPU from Intel, you just assign one core to each possible permutation, and add up the costs (this is fast), and see if any core flags a success.
More generally, a problem in NP is a decision problem such that a potential solution can be verified in polynomial time (i.e., efficiently), and so (since the potential solutions are enumerable) any such problem can be efficiently solved with sufficiently many CPUs.
David Thornley
2010-03-29 16:52:46
Sure, you can enumerate all possible solutions, but how to provide every processing unit with required data? You have to distribute data and it means you have to compare each permutation with each other one.
psihodelia
2010-03-29 17:17:01
No, you don't have to compare everything to everything. Suppose you wanted the lowest-cost solution to a TSP. Calculate all costs in parallel. Then even-numbered CPUs compare their values with corresponding odd ones, and keep the more economical result. Do that sort of comparison, and you can get the answer in the time needed for log n! comparisons. O(n^n) >= O(n!), and log (n^n) is n log n, so the post-processing would be at worst O(n log n), which is polynomial. It would be possible to do at least as well on setup.
David Thornley
2010-03-29 18:07:15
@David Thornley: Let's look at TSP, which is: Given a complete weighted graph find a Hamiltonian cycle with the least weight. You has to have a deterministic procedure to produce an unique Hamiltonian cycle on each CPU. You must assign every possible cycle to every CPU. Even if calculating a cycle's length can be done in a completely independent processing thread, there are n! cycles. The question is then: can all cycles be assigned to CPUs independently? No. Why? Because of the deterministic nature of the reckoning.
psihodelia
2010-03-29 19:20:56
@psihodelia: It's not that horribly difficult to determine the nth permutation, and you must assign every possible cycle to **one** CPU, not every CPU. Splitting up the problem is certainly no worse than O(log n!), or O(n log n). I completely fail to understand your last sentence: certainly this is easier, not harder, because of the deterministic nature, which means that a CPU tasked with calculating the Kth permutation can do so, and with K running from 1 to n! that covers the solution set precisely.
David Thornley
2010-03-29 20:11:36
+6
A:
It sounds like what you're really asking is whether a problem of O(n!) complexity can be reduced to O(n^a) on a non-deterministic machine; in other words, whether Not-P = NP. The answer to that question is no, there are some Not-P problems that are not NP. For example, a limited halting problem (that asks if a program halts in at most n! steps).
tloflin
2010-03-29 16:56:37
I took the answer to be if there are some problems that can be easily solved. You are answering for all problems, which is equally legitimate and what most people answering didn't address.
David Thornley
2010-03-29 18:12:03
That's true. I think our answers are complementary: there are some problems which do reduce and others which do not. Both facts are important.
tloflin
2010-03-29 18:20:42
+2
A:
The problem would be distributing the work and collecting the results.
If all the CPUs can read the same piece of memory at once, and if each one has a unique CPU-ID that is known to it, then the ID may be used to select a permutation, and the distribution problem is solveable in constant time.
Gathering the results would be tricky, though. Each CPU could compare with its (numerical) neighbor, and then that result compared to the result of the two closest neighbors, etc. This will be a O(log(n!)) process. I don't know for sure, but I suspect that O(log(n!)) is hyperpolynomial, so I don't think that's a solution.
Jeffrey L Whitledge
2010-03-29 16:59:20
+1
A:
If the problem is one of checking permutations/answers to a problem of complexity O(n!), then of course you can do it efficiently with an infinite number of processors.
The reason is that you can easily distribute atomic pieces of the problem (an atomic piece of the problem might, say, be one of the permutations to check) with logarithmic efficiency.
As a simple example, you could set up the processors as a 'binary tree', so to speak. You could be at the root, and have the processors deliver permutations of the problem (or whatever the smallest pieces of the problem might be) to the leaf processors to solve, and you'd end up solving the problem in log(n!) time.
Remember it's the delivery of the permutations to the processors that takes a long time. Each part of the problem itself will actually be solved instantly.
Edit: Fixed my post according to the comments below.
Cam
2010-03-29 17:01:11
Since number of CPUs used on the problem is n! rather than n, the 'binary tree' setup is on the order of log(n!).
Jeffrey L Whitledge
2010-03-29 17:05:16
log n! is good enough. It's polynomial (although definitely not sublinear).
David Thornley
2010-03-29 18:08:51
A:
Each problem could be solved by one CPU, but who would deliver these jobs to all infinite CPU's? In general, this task is centralized, so if we have infinite jobs to deliver to all infinite CPU's, we could take infinite time to do so.
Juliano
2010-03-29 17:03:07
Actually, for most real problems distributing the jobs is a parallel process, so for O(n!) problems distribution is O(n log n).
David Thornley
2010-03-29 18:10:32
+1
A:
No, N! is even higher than NP. Thinking unlimited parallelism could solve NP problem in polynomial time, which is usually considered as a "reasonable" time complexity, N! problem is still higher than polynomial on such a setup.
Codism
2010-03-29 17:28:20
*N! is even higher than NP* — [citation needed]. And is it even relevant? As long as the result is verifiable in polynomial time it is in NP.
KennyTM
2010-03-29 17:39:55
It's reasonable to say that O(n!) is higher than O(2^n), since that's comparing like with like. However, an NP problem is defined as one that's solvable in polynomial time on a nondeterministic Turing machine, or equivalently, with results that are verifiable in polynomial time. It says nothing about the time complexity for finding a solution. Therefore, I simply don't understand what you can mean by your statement.
David Thornley
2010-03-29 17:51:48
@KennyTM: Apologize for abusing the NP notation. I somehow perceived that NP problems have the form of k^N, maybe because of the omnipotence of its academic definition. You are right, I should have not used NP in my originally response and there is no citation for my statement. However, if a problem is verifiable in polynomial time defers from problem to problem. My original intention was to say there are some problems with N! complexity cannot be verified in polynomial time even with unlimited parallelism.
Codism
2010-03-30 04:10:45
+1
A:
You mentioned search as a "typical" problem, but were you actually asked specifically about a search problem? If so, then yes, search is typically parallelizable, but as far as I can tell O(n!) in principle does not imply the degree of concurrency available, does it? You could have a completely serial O(n!) problem, which means infinite computers won't help. I once had an unusual O(n^4) problem that actually was completely serial.
So, available concurrency is the first thing, and IMHO you should get points for bringing up Amdahl's law in an interview. Next potential pitfall is inter-processor communication, and in general the nature of the algorithm. Consider, for example, this list of application classes: http://view.eecs.berkeley.edu/wiki/Dwarf_Mine. FWIW the O(n^4) code I mentioned earlier sort of falls into the FSM category.
Another somewhat related anecdote: I've heard an engineer from a supercomputer vendor claim that if 10% of their CPU time were being spent in MPI libraries, they consider the parallelization a solid success (though that may have just been limited to codes in the computational chemistry domain).
tramdas
2010-03-29 17:53:46
+1
A:
This is like asking if an infinite number of monkeys typing on a monkey-destruction proof computer with a word-processor can come up with all the works of Shakespeare; given an infinite amount of time. The realist would say not since the conditions are no physically possible. The idealist will say yes; in theory it can happen. Since Software Engineering (Software Engineering, not Computer Science) focuses on real system we can see and touch, then the answer is no. If you doubt me, then go build it and prove me wrong! IMHO.
Phil
2010-03-29 18:03:15
+1
A:
Sometimes the correct answer is, "How many times does this come up with your code base?" but in this case, there is a real answer.
The correct answer is no, because not all problems can be solved using perfect parallel processing. For example, a travelling salesman-like problem must commit to one path for the second leg of the journey to be considered.
Assuming a fully connected matrix of cities, should you want to display all possible non-cyclic routes for our weary salesman, you're stuck with a O(n!) problem, which can be decomposed to an O(n)*O((n-1)!) problem. The issue is that you need to commit to one path (on the O(n) side of the equation) before you can consider the remaining paths (on the O((n-1)!) side of the equation).
Since some of the computations must be performed prior to other computations, then there is no way to scatter the results perfectly in a single scatter / gather pass. That means the solution will be waiting on the results of calculations which must come before the "next" step can be started. This is the key, as the need for prior partial solutions provide a "bottle neck" in the ability to proceed with the computation.
Since we've proven we can make a number of these infinitely fast, infinitely numerous, CPUs wait (even if they are waiting on themselves), we know that the runtime cannot be O(1), and we only need to pick a very large N to guarantee an "unacceptable" run time.
Edwin Buck
2010-03-29 19:21:07
Nope. Distribute permutations among CPUs, which is a polynomial-time operation. Each CPU then calculates its permutation cost, which is also polynomial-time, actually O(n). Then there comes the hierarchical comparison, which is also polynomial-time.
David Thornley
2010-03-29 20:14:11
You can't distribute all permutations among the CPUs without having explored the permutation space. If you took a shotgun approach, you might miss permutations (and there would definitely be a lot of overlap) and the "recombination phase" would pay the price of having to sort through tons of duplicates, which would still take it above O(1) making it still subject to "unreasonable time" by making the solution set large enough.
Edwin Buck
2010-03-29 22:23:45