Linked Questions
14 questions linked to/from Why polynomial time is called "efficient"?
10
votes
2
answers
1k
views
Why do we say that polynomial time is easy? [duplicate]
For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so.
...
- 101
0
votes
0
answers
48
views
Why are polynomials a natural measure for easiness of computational problems? [duplicate]
We understand the exponential function to constantly grow, which we consider bad for a problem. By constantly growing I mean the ratio
$\frac{f(n+1)}{f(n)}$
never tends to 1, where $f(n)$ is the ...
1
vote
0
answers
38
views
Besides practical computing applications, is there a reason polynomial is "good" and exponential is "bad"? [duplicate]
The overarching theme of computer science seems to be that polynomial time or space or what-have-you for an algorithm is a success, and exponential is a failure. The definitions of P and NP revolve ...
- 497
11
votes
6
answers
12k
views
What is an Efficient Algorithm?
From the point of view of asymptotic behavior, what is considered an "efficient" algorithm? What is the standard / reason for drawing the line at that point? Personally, I would think that anything ...
- 2,931
9
votes
3
answers
764
views
Why are most (or all?) polynomial time algorithms practical?
I read an interesting comment in a paper recently about how weirdly useful maths turns out to be. It mentions how polynomial time doesn't have to mean efficient in reality (e.g., $O(n^{...
- 91
5
votes
2
answers
1k
views
Why is it important to solve a problem in Polynomial time, In cryptography?
I have just started to learn Cryptography.
I am trying to learn "Merkle-Hellman Knapsack Cryptosystem".
So, right at the beginning of the discussion, a question came in my mind:
Why is it important ...
user30671
2
votes
1
answer
592
views
Why are problems in P easy and other problems not
Problems in $P$ have polynomial time algorithms. Problems in e.g. $NP-complete$ are only solvable in "probably exponential time" (Shen Lin's PET).
Problems in $P$ are considered easy while others (...
- 1,314
3
votes
1
answer
420
views
Why Study Complexity Theory?
I’m an amateur in the study of algorithms. For a while I’ve had a burning question, why do we study complexity theory in computer science? The reason I ask is because algorithms with better ...
- 143
3
votes
1
answer
705
views
How to Define an Efficient, Optimal or Suboptimal Parallel Algorithm?
I am going through the book of Parallel Programming and a parallel algorithm is often classified as Efficient, Optimal or Suboptimal. I googled these terms but I didn't found a clear definition for ...
0
votes
1
answer
469
views
How is the formal definition of NP-hard equivalent to this colloquial one?
Wikipedia informally describes NP-hard problems as "at least as hard as the hardest problems in NP".
It then states the formal definition: "a problem H is NP-hard when every problem L in NP can be ...
- 163
3
votes
1
answer
168
views
Does proving a problem is in P typically mean it will eventually be practically solvable?
I'm currently reading Introduction to the Theory of Computation by Michael Sipser and in his section on time complexity, he tries to justify why theoretical computer scientists divide problems into P ...
- 133
2
votes
2
answers
120
views
Does the word "efficient" usually refer to polynomial time or polylogarithmic time?
This question is strictly about terminology.
I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and ...
- 1,116
1
vote
1
answer
193
views
Finding a match in two collections
Let $A$ and $B$ be two one-dimensional, finite collections of unsigned integers (e.g. arrays). Furthermore, $card(A) = a < b = card(B)$. Both collections are sorted in ascending order. There is at ...
- 11
2
votes
1
answer
85
views
Can computation models be categorized in terms of efficiency?
It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other ...
- 4,159