Mixing
Linear Programming Confusion about Complexity
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
In the wiki page of Linear Programming is told that Linear Programming problems belong to P complexity class.
However, the method generally used to solve Linear Programming problems is the Simplex method that not belong to P. So, does this make Linear Programming problems exponentially complex ?
linear-programming
asked Jul 17 at 6:48
Koinos
565
add a comment |Â
up vote
0
down vote
favorite
In the wiki page of Linear Programming is told that Linear Programming problems belong to P complexity class.
However, the method generally used to solve Linear Programming problems is the Simplex method that not belong to P. So, does this make Linear Programming problems exponentially complex ?
linear-programming
asked Jul 17 at 6:48
Koinos
565
the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. simplex method has polynomial smoothed complexity. Please check: Complexity of the simplex algorithm
– W.R.P.S
Jul 17 at 7:55
As example Quick sort has worst complexity of $O(n^2)$ but it's still preferred instead of merge sort with $O(nlog n)$ worst complexity.
– kingW3
Jul 17 at 9:21
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
In the wiki page of Linear Programming is told that Linear Programming problems belong to P complexity class.
However, the method generally used to solve Linear Programming problems is the Simplex method that not belong to P. So, does this make Linear Programming problems exponentially complex ?
linear-programming
asked Jul 17 at 6:48
Koinos
565
In the wiki page of Linear Programming is told that Linear Programming problems belong to P complexity class.
However, the method generally used to solve Linear Programming problems is the Simplex method that not belong to P. So, does this make Linear Programming problems exponentially complex ?
linear-programming
asked Jul 17 at 6:48
Koinos
565
asked Jul 17 at 6:48
Koinos
565
asked Jul 17 at 6:48
Koinos
565
asked Jul 17 at 6:48
Koinos
565
565
the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. simplex method has polynomial smoothed complexity. Please check: Complexity of the simplex algorithm
– W.R.P.S
Jul 17 at 7:55
As example Quick sort has worst complexity of $O(n^2)$ but it's still preferred instead of merge sort with $O(nlog n)$ worst complexity.
– kingW3
Jul 17 at 9:21
add a comment |Â
the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. simplex method has polynomial smoothed complexity. Please check: Complexity of the simplex algorithm
– W.R.P.S
Jul 17 at 7:55
As example Quick sort has worst complexity of $O(n^2)$ but it's still preferred instead of merge sort with $O(nlog n)$ worst complexity.
– kingW3
Jul 17 at 9:21
the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. simplex method has polynomial smoothed complexity. Please check: Complexity of the simplex algorithm
– W.R.P.S
Jul 17 at 7:55
the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. simplex method has polynomial smoothed complexity. Please check: Complexity of the simplex algorithm
– W.R.P.S
Jul 17 at 7:55
As example Quick sort has worst complexity of $O(n^2)$ but it's still preferred instead of merge sort with $O(nlog n)$ worst complexity.
– kingW3
Jul 17 at 9:21
As example Quick sort has worst complexity of $O(n^2)$ but it's still preferred instead of merge sort with $O(nlog n)$ worst complexity.
– kingW3
Jul 17 at 9:21
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
Linear Programming can be solved in polynomial time with ellipsoid algorithms.
However, in practice, the simplex algorithm is more efficient, despite the fact that its worst time run times are exponential.
So in summary : linear programming problems are not "exponentially complex", but they are typically solved with an algorithm that may run in exponential times in worst case scenarios.
answered Jul 17 at 7:47
Kuifje
6,8112523
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Linear Programming can be solved in polynomial time with ellipsoid algorithms.
However, in practice, the simplex algorithm is more efficient, despite the fact that its worst time run times are exponential.
So in summary : linear programming problems are not "exponentially complex", but they are typically solved with an algorithm that may run in exponential times in worst case scenarios.
answered Jul 17 at 7:47
Kuifje
6,8112523
add a comment |Â
up vote
3
down vote
accepted
Linear Programming can be solved in polynomial time with ellipsoid algorithms.
However, in practice, the simplex algorithm is more efficient, despite the fact that its worst time run times are exponential.
So in summary : linear programming problems are not "exponentially complex", but they are typically solved with an algorithm that may run in exponential times in worst case scenarios.
answered Jul 17 at 7:47
Kuifje
6,8112523
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Linear Programming can be solved in polynomial time with ellipsoid algorithms.
However, in practice, the simplex algorithm is more efficient, despite the fact that its worst time run times are exponential.
So in summary : linear programming problems are not "exponentially complex", but they are typically solved with an algorithm that may run in exponential times in worst case scenarios.
answered Jul 17 at 7:47
Kuifje
6,8112523
Linear Programming can be solved in polynomial time with ellipsoid algorithms.
However, in practice, the simplex algorithm is more efficient, despite the fact that its worst time run times are exponential.
So in summary : linear programming problems are not "exponentially complex", but they are typically solved with an algorithm that may run in exponential times in worst case scenarios.
answered Jul 17 at 7:47
Kuifje
6,8112523
answered Jul 17 at 7:47
Kuifje
6,8112523
answered Jul 17 at 7:47
Kuifje
6,8112523
answered Jul 17 at 7:47
Kuifje
6,8112523
6,8112523
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854223%2flinear-programming-confusion-about-complexity%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. simplex method has polynomial smoothed complexity. Please check: Complexity of the simplex algorithm
– W.R.P.S
Jul 17 at 7:55
As example Quick sort has worst complexity of $O(n^2)$ but it's still preferred instead of merge sort with $O(nlog n)$ worst complexity.
– kingW3
Jul 17 at 9:21