Minimum relevant variables in linear system: Difference between revisions

Revision as of 01:39, 27 December 2019

Revision as of 14:21, 25 January 2021

Line 36:

*Min-ULR[=] cannot be approximated within a factor of <math>2^{\log^{1-\varepsilon}n}</math>, for any <math>\varepsilon>0</math>, unless NP is contained in [[DTIME]](<math>n^{\operatorname{polylog}(n)}</math>). <ref>{{Cite journal|date=1997-04-01|title=The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations|journal=Journal of Computer and System Sciences|language=en|volume=54|issue=2|pages=317–331|doi=10.1006/jcss.1997.1472|issn=0022-0000|last1=Arora|first1=Sanjeev|last2=Babai|first2=László|last3=Stern|first3=Jacques|last4=Sweedyk|first4=Z.}}</ref>

In the complementary problem '''MAXimum Feasible Linear SubystemSubsystem''' ('''Max-FLS'''), the goal is to find a maximum subset of the constraints that can be satisfied simultaneously.<ref name=":0" />

* Max-FLS[≠] can be solved in polynomial time.