Systems of linear inequalities

AI Thread Summary
There is no known polynomial time algorithm specifically for solving systems of linear inequalities that is efficient in terms of the number of input constraints and variables. The Simplex algorithm, while commonly used, has exponential worst-case performance. Karmarkar's algorithm can solve these systems but operates at a complexity of n^3.5*L^2, which is not polynomial time. The discussion highlights the search for faster algorithms to determine the existence of solutions for such systems. Overall, the quest for a more efficient solution remains an open question in computational mathematics.
sid_galt
Messages
502
Reaction score
1
Hi,
Is there a polynomial time algorithm (polynomial time in terms of the number of input constraints and variables) to solve a system of linear inequalities or or indicate whether a solution for a system of linear inequalities exists or not?
Thanks
 
Last edited:
Mathematics news on Phys.org
Polynomial time Simplex?
 
Simplex is exponential in the worst-case. Although there's Karmarkar's algorithm, it is for optimization of an objective function. Although it can be used for solving systems of linear inequalities, it takes n^3.5*L^2 time. I was wondering if there was a faster algorithm for giving a solution to the systems of linear inequalities.
 
Thread 'Video on imaginary numbers and some queries'

Thread 'Video on imaginary numbers and some queries'

Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »
Thread 'Unit Circle Double Angle Derivations'

Thread 'Unit Circle Double Angle Derivations'

Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
View full post »

Similar threads

I What Are the Benefits of Triangle Inequality in Mathematics?
Replies
2
Views
2K
MHB How to Graph a System of Inequalities for Investment Allocation?
Replies
16
Views
2K
B Problem with simple inequality
Replies
13
Views
2K
I Relevant Literature for Noisy Linear Dynamical Systems
Replies
1
Views
2K
MHB What Are the Solutions to the System of Inequalities for Target Heart Rate?
Replies
3
Views
1K
MHB Solving system of linear inequalities
Replies
9
Views
3K
B What do we mean when we say that x∈R
Replies
21
Views
6K
MHB Which Quadrant Contains No Solutions to This System of Inequalities?
Replies
2
Views
3K
Can this system of inequalities be solved for x?
Replies
5
Views
1K
I Bohmian Prediction of Bell Inequality Violations
Replies
45
Views
4K

Hot Threads

Recent Insights

Back
Top