[macosxnerd101]

Quote

Is this also an example of

No. The domain is defined to be binary strings. The solution is linear for all finite lists of binary elements.

Essentially what it is doing is counting the number of 1's, you are correct. So starting at index = 1, ..., n, use a threshold function. Each threshold function can be executed in parallel, so all of those occur in one time step. However, additional space is required to execute each threshold function in parallel. It's a space-time tradeoff, which is accomplished with a parallel prefix.

[AdamSpeight2008]

It's a parallel algorithm, which is kinda of cheating.

[macosxnerd101]

Not really. Binary sort is studied in circuit theory. The space complexity is really the circuit size complexity; and the time complexity is really the circuit depth complexity. If I only have one threshold circuit and I need to run the function n times, then I take n * T(n) time, where T(n) is the complexity of the threshold function. If I have multiple threshold circuits, my space complexity goes up but my time complexity goes down. You may also be interested in reading more on Parallel Prefix operations.

[AdamSpeight2008]

In Circuit design different rules apply. Parallelism is reasonable cheap and often exploited.

It doesn't require N circuits though, and it can't be applied to a classical "non-parallel" processor though.

[Fooality]

jon.kiparsky, on 12 December 2013 - 05:10 PM, said:

Anyway, the point is, what's changed in the situation you describe is the problem, not its complexity. I would suggest, if you have plenty of spare time, that you might want to take a peek at Jeff Ullman's Automata Theory course on Coursera. This will lead you up to a more effective understanding of the NP-complete languages. (and it's nice in that it's very self-contained. There's almost nothing that you need to know going in, all of the primitives outside of some very basic logic and set theory are constructed in the early lectures)

Thanks to all of you to your great responses, and for the course recommendation. I thank you for your patience, I can be bad at communicating about this stuff.

To jon: The main thing is, I'm not concerned with the complexity of the traveling salesman problem at all. If the the function that solves the traveling salesman problem is T(N) (where N is a set of locations on a map, and T(N) is a vector that contains all the locations in the shortest possible order) then what I'm interested in the complexity of some function A(n), where A(n) = T(L(n)). If the range of the internal function L(n) is exactly equivalent to the domain of T(N), then the complexity of A is equal the complexity of T. However if its not...

Even though a solution for ALL the elements in the domain of T may not have a solution in polynomial time, subsets of the domain CAN have solutions in polynomial time, which is what I was saying. One obvious example of such a subset for T(N) is the set where all the locations lay on a horizontal line, in which case - yes - all you have to do is sort them. But there are more subsets of the domain of T(n) like that, including a whole bunch that who's polynomial time solutions are not obvious, but exist. If the range of the function L(n) all falls within one of those non obvious polynomial-time-solvable subsets of the domain of T(N), then a not obvious, polynomial time solution to A(n) exists. If we can't see that non-obvious solution though, and how to solve it, our best solution runs in greater than polynomial time.

So in this sense, we have a problem, A(n), who's best solution is in greater than polynomial time, until we realize that a solution exists in polynomial time. So our implementation of A(n) goes from outside P, to inside P.

That's the point I was making. An example in the real world: Alice makes a public key cryptography system, in which getting the private key from the public key requires factoring a very large number, which is the product of two very large primes which another algorithm she made has generated. Since the function FACTOR(n) is known to have no solution in polynomial time, Alice trusts her system is secure. However, if the function which generates her pairs of primes has a range which maps into some not-obvious subset of the domain of FACTOR which have solutions in polynomial time, and that function is public, than her cryptosystem is not secure. Because her whole equation is actually FACTOR(MULITPLY(GET_PRIME_PAIR(n))) if the range of MULITPLY(GET_PRIME_PAIR(n)) falls in whole or part into the wrong subset of the domain of FACTOR(n), then all the rules change.

[macosxnerd101]

That's the point though- the problem either is or isn't in P. We don't look at specific instances. It doesn't make sense to talk about a specific instance being in P. That's why it's clearer and easier to understand if you think about this in terms of formal languages. The entire language must be reduced in log space to a P complete language. Note that a log space reduction implies polynomial time. The other big point with P is determinism. This means the FSM will determine whether or not a string is in the language. NP is non deterministic. If a string is in the language, you'll get a yes. Otherwise, you may get a no or the FSM may not halt.

[macosxnerd101]

Quote

Since the function FACTOR(n) is known to have no solution in polynomial time, Alice trusts her system is secure.

Integer factorization is not NP-complete. More likely than not, it is in P. In fact, quantum computing makes factoring cake work, so it probably is in P.

[mojo666]

Fooality, you seem a bit confused about a few things. First of all, the op is asking about np complete problems, not just np problems. np complete problems are a subset of np problems. np complete problems are a specific set of problems that have been shown to be equivalent. Thus if we are able to show that one of them is in p, then all of them are in p. So far, no one has been able to show that they are p which is what the op was asking.

You also seem to misunderstand complexity. The point of complexity is to tell us how our algorithm will perform as the input changes (more specifically as input gets bigger). When I write an algorithm to handle my 10 customers, I want to make sure my programming is solid enough to take on additional customers and keep running smoothly when I am up to 100,000 customers. If my algorithm has exponential behavior, then it probably will not handle many customers very well and I need to find a better solution. Thus it makes no sense to talk about complexity "for a given n". If the input is constant or bounded by size, then the run time is constant or bounded in run time. Without any variance in input, there is no sufficient variance in runtime. Even if the runtime for a specific constant algorithm is a really long time, it is still a constant time. Thus you are not really talking about complexity and can't really be commenting on p or np.

[Fooality]

mojo666, on 13 December 2013 - 11:05 AM, said:

You also seem to misunderstand complexity. The point of complexity is to tell us how our algorithm will perform as the input changes (more specifically as input gets bigger). When I write an algorithm to handle my 10 customers, I want to make sure my programming is solid enough to take on additional customers and keep running smoothly when I am up to 100,000 customers. If my algorithm has exponential behavior, then it probably will not handle many customers very well and I need to find a better solution. Thus it makes no sense to talk about complexity "for a given n". If the input is constant or bounded by size, then the run time is constant or bounded in run time. Without any variance in input, there is no sufficient variance in runtime. Even if the runtime for a specific constant algorithm is a really long time, it is still a constant time. Thus you are not really talking about complexity and can't really be commenting on p or np.

I do understand complexity. All I'm saying can be reduced down to a very simple programming problem. I'm going to hand you a computer function L(n) who's input is a natural number. Its going to produce a list of N locations, as (x, y) tuples, its going to take n steps to do this. Then you're going to write a function which finds the shortest path between all of them, and outputs it as a vector of n locations. Well call it T. So the whole thing is T(L(n))

The question is how many steps will this program take? Will it take n! steps? Will it take n^2 steps? Will it take log(n)n steps?

The answer is that if you know nothing about the output of L(n), your program will have to address every contingency, and take the same amount of time to solve as the travelling salesman problem. (plus n, from L) The whole problem is thus in the same complexity class as the travelling salesman problem. However if you know about the outputs of L(n), and you know they have a certain quality, like they all lie on a horizontal line, the complexity of the problem is dramatically reduced, which is to say your code now takes many less steps than it did before for a given n. The outputs of L(n) may have this quality in a way that's really hard to see, but is there. So lets look at the whole picture.

A) We had a problem, and our best attempts to solve it took as many steps as the travelling salesman problem.
We learned something new about the problem, and it gave us a way to solve it way faster, like in polynomial or n*log(n) time.

Now you can call that an abuse or misuse of theoretical terms, to say our problem went from NP to P by learning more about L, and it may be, but the gist is correct. I'm not saying P = NP or anything like that, I'm saying that there are problems, where out best solutions may be NP-hard, until we discover very fast solutions.

[macosxnerd101]

Quote

A) We had a problem, and our best attempts to solve it took as many steps as the travelling salesman problem.
/> We learned something new about the problem, and it gave us a way to solve it way faster, like in polynomial or n*log(n) time.

Now you can call that an abuse or misuse of theoretical terms, to say our problem went from NP to P by learning more about L, and it may be, but the gist is correct. I'm not saying P = NP or anything like that, I'm saying that there are problems, where out best solutions may be NP-hard, until we discover very fast solutions.

This is exactly what is happening (a misuse of formal terminology, as well a misunderstanding of the theory). The traveling salesman problem could be better described as a class of problems, so a single instance falls into the class of TSP.

Quote

I'm saying that there are problems, where out best solutions may be NP-hard, until we discover very fast solutions.

You are saying we can solve certain instances of hard problems by approximations and clever approaches. You are saying nothing about the class of problem from which it comes.

Again- look at this with a formal languages insight rather than an algorithm analysis insight.

[Fooality]

macosxnerd101, on 13 December 2013 - 03:28 PM, said:

You are saying we can solve certain instances of hard problems by approximations and clever approaches. You are saying nothing about the class of problem from which it comes.

Again- look at this with a formal languages insight rather than an algorithm analysis insight.

That is correct, I'm saying nothing about the class of problem from which it comes (the travelling salesman problem), but I'm not talking about approximations. What I'm asking (and I'll avoid any terminology here) is how many steps does it take to solve some problem A, where A(n) = T(L(n)) and T solves the travelling salesman problem? And what I'm saying is that the answer to that question depends on an understanding of of the range (outputs) of L as it relates to the domain (inputs) of T. I'm saying the amount of steps it takes for an algorithm to solve A is dependent on a the subset (or "instances") of T, that correspond to the outputs of L, and that the solution to the whole problem A is equivalent to those instances. Point is:

The amount of steps is takes to solve a problem can be a function of how much you know about it.

[macosxnerd101]

Quote

The amount of steps is takes to solve a problem can be a function of how much you know about it.

I think everyone will agree to that. Not to be snarky though, but that's a fairly trivial/obvious statement/point.

[Fooality]

macosxnerd101, on 13 December 2013 - 04:11 PM, said:

Quote

The amount of steps is takes to solve a problem can be a function of how much you know about it.

I think everyone will agree to that. Not to be snarky though, but that's a fairly trivial/obvious statement/point. />

Thank you! I'm understood! That's the whole point I was making all this time. There are problems for which our best solution (due to lack of knowledge) runs in exponential time, which actually have solutions in polynomial time. This whole thread/conversation seems to humorously illustrates that point.

That fact isn't as trivial as it sounds though. In the example I gave, Alice's secret pair of primes was secured by the fact that it took greater than polynomial time to find it. However it wasn't actually secure, because her prime pair generator only output "instances" which had solutions in polynomial time, which an attacker could use...

[macosxnerd101]

Quote

There are problems for which our best solution (due to lack of knowledge) runs in exponential time

Remove the (due to lack of knowledge) part and you will be correct.

Quote

which actually have solutions in polynomial time.

No. This is where your confusion is. There are many problems computers cannot solve. In fact, most boolean functions (ie., something a computer would execute), require exponential time. There are bounds on this. I can pull them from my Theory of Computation textbook if you would like.

[jon.kiparsky]

Fooality, I think we're all agreed that if you restrict a problem to a limited domain, you can use that knowledge to devise a more efficient algorithm. To take an extreme case, I can sort a list of numbers in O(0), if I know that the list is already sorted.

I understand what you're saying: that when we approach a given programming problem we should make use of all the information we have available to us. In practical terms, you're right. If we happen to know, for example, that our traveling salesman is visiting just some number of trains on a single railroad line, and we're only interested in minimizing the distance they travel, then we have an easy problem. We can solve the problem of this salesman's itinerary in polynomial time.

However, I'm going to insist that this has not got anything to do with a problem that had been NP-complete getting solved in polynomial time. That problem was in P all along, so it was never NP-complete to begin with. This is because to be NP-complete, and to be NP-complete, we need to be able to show a reduction from every NP-complete problem to this one. That is, we need to display an algorithm for every NP-complete language that transforms an instance of that language to an instance of this one.

I'm willing to concede that you've taken an instance which could be reduced to the TSP and shown that it can be solved in polynomial time, but that is profoundly uninteresting. There are many instances of the TSP that can be solved in P. Finding special cases and solving them is a good programming practice, but it has nothing at all to do with the question that was posed. The answer to that question is, "not yet, so you can keep buying things on line".