Is there a polynomial time algorithm determine whether a given point $x$ is a basic feasible solution(vertex solution) of polyhedron $P$ Given a polyhedron $P \subset \mathbb{R^n}$ defined by $m$ inequalites $Ax \leq b$. Given a point $z \in \mathbb{R^n}$, is there a polynomial time algorithm to determine if $z$ is a basic feasible solution(vertex solution) of $P$?
Yes, just compute $Az.$ If it is equal to $b,$ then check how many constraints are violated for $z + \epsilon A_i$ (where $A_i$ is the $i$-th row.)
Yes, just compute $Az.$ If it is equal to $b,$ then check how many constraints are violated for $z + \epsilon A_i$ (where $A_i$ is the $i$-th row.)