
\section{Introduction}

Degenerate input can be an issue in structural analysis and algorithm design for many algebraic and geometric problems. 
It is often swept under the rug by assuming the input to be non-degenerate. For example, one often assumes all input points of a geometric problem to be in general position. In some problems (e.g., the minimum convex partition~\cite{grelier2022minimumconvexpartition}), such an assumption is inappropriate as it makes the problem considerably easier. 
In other cases, degenerate inputs can be solved easily by resolving degeneracy using \emph{perturbation} techniques.

In this paper, we investigate degeneracy in the context of the \acrfull{POMCP}. Assuming non-degeneracy, this problem can be solved by converting it into a Unique Sink Orientation of the hypercube graph, and finding a sink within that orientation. Oriented matroids are abstractions for many types of configurations of geometric objects, such as (pseudo-)hyperplane arrangements or point configurations. Just like these geometric configurations, oriented matroids can exhibit degeneracies. In this paper, we analyze the effects of these degeneracies on the reduction from \gls*{POMCP}\xspace to Unique Sink Orientation sink-finding. 

Both the \gls*{POMCP}\xspace as well as Unique Sink Orientations are combinatorial abstractions of the \PLCP. The complexity status of the \PLCP remains an interesting and relevant open question, since the problem can be used to solve many optimization problems, such as Linear Programming~\cite{gaertner2006lpuso}, and binary Simple Stochastic Games~\cite{gaertner2005stochasticgames,ruest2007phd}. Sink-finding in Unique Sink Orientations can also be used to solve geometric problems such as the problem of finding the smallest enclosing ball of a set of balls~\cite{fischer2004smallestball}.


\section{Background}
\subsection{Oriented Matroids}\label{sec:OMPrelims}

For a more extensive introduction to oriented matroids, we refer the reader to the comprehensive textbook by Björner et al.~\cite{bjoerner1999orientedmatroids}. We consider oriented matroids $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E,\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ in \emph{circuit representation}, where $E$ is called the \emph{ground set}, and $\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$ is the collection of circuits of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$.

A \emph{circuit} $\relax\ifmmode{X}\else{$X$}\fi\xspace\in\{-,0,+\}^{E}$ is a \emph{signed set} represented by a tuple of sets $\relax\ifmmode{X}\else{$X$}\fi\xspace = (\relax\ifmmode{X}\else{$X$}\fi\xspace^+, \relax\ifmmode{X}\else{$X$}\fi\xspace^-)$
where for all $\relax\ifmmode{e}\else{$e$}\fi\xspace \in \relax\ifmmode{X}\else{$X$}\fi\xspace^+ \colon \relax\ifmmode{X}\else{$X$}\fi\xspace_\relax\ifmmode{e}\else{$e$}\fi\xspace = +$ and $\relax\ifmmode{e}\else{$e$}\fi\xspace \in \relax\ifmmode{X}\else{$X$}\fi\xspace^- \colon  \relax\ifmmode{X}\else{$X$}\fi\xspace_\relax\ifmmode{e}\else{$e$}\fi\xspace = -$. 
We write $-\relax\ifmmode{X}\else{$X$}\fi\xspace$ for the inversed signed set $-\relax\ifmmode{X}\else{$X$}\fi\xspace =  (\relax\ifmmode{X}\else{$X$}\fi\xspace^-, \relax\ifmmode{X}\else{$X$}\fi\xspace^+)$.
The \emph{support} is defined as the set of non-zero elements $\support{\relax\ifmmode{X}\else{$X$}\fi\xspace} \coloneqq \relax\ifmmode{X}\else{$X$}\fi\xspace^+ \cup \relax\ifmmode{X}\else{$X$}\fi\xspace^-$. 


\begin{definition}[Circuit axioms]
For an oriented matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace = (\relax\ifmmode{E}\else{$E$}\fi\xspace, \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ on the ground set $\relax\ifmmode{E}\else{$E$}\fi\xspace$ the following set of axioms are satisfied for $\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$:
\begin{itemize}[leftmargin=1.2cm]
\item[(C0)] $(\emptyset, \emptyset) \notin \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$.
\item[(C1)] $X\in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace \Leftrightarrow -X\in\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$.
\item[(C2)] For all $\relax\ifmmode{X}\else{$X$}\fi\xspace, \relax\ifmmode{Y}\else{$Y$}\fi\xspace \in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$, if $\support{\relax\ifmmode{X}\else{$X$}\fi\xspace}\subseteq \support{\relax\ifmmode{Y}\else{$Y$}\fi\xspace}$, then $\relax\ifmmode{X}\else{$X$}\fi\xspace=\relax\ifmmode{Y}\else{$Y$}\fi\xspace$ or $\relax\ifmmode{X}\else{$X$}\fi\xspace=-\relax\ifmmode{Y}\else{$Y$}\fi\xspace$.
\item[(C3)] For all $\relax\ifmmode{X}\else{$X$}\fi\xspace, \relax\ifmmode{Y}\else{$Y$}\fi\xspace \in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$, $\relax\ifmmode{X}\else{$X$}\fi\xspace\neq-\relax\ifmmode{Y}\else{$Y$}\fi\xspace$, and $\relax\ifmmode{e}\else{$e$}\fi\xspace \in \relax\ifmmode{X}\else{$X$}\fi\xspace^+ \cap \relax\ifmmode{Y}\else{$Y$}\fi\xspace^-$ there is a $\relax\ifmmode{Z}\else{$Z$}\fi\xspace \in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$ such that
\begin{itemize}
\item $\relax\ifmmode{Z}\else{$Z$}\fi\xspace^+ \subseteq (\relax\ifmmode{X}\else{$X$}\fi\xspace^+ \cup \relax\ifmmode{Y}\else{$Y$}\fi\xspace^+) \setminus \{\relax\ifmmode{e}\else{$e$}\fi\xspace\}$ and 
\item $\relax\ifmmode{Z}\else{$Z$}\fi\xspace^- \subseteq (\relax\ifmmode{X}\else{$X$}\fi\xspace^- \cup \relax\ifmmode{Y}\else{$Y$}\fi\xspace^-) \setminus \{\relax\ifmmode{e}\else{$e$}\fi\xspace\}$.
\end{itemize}
\end{itemize}
\end{definition}

A \emph{basis} $\relax\ifmmode{B}\else{$B$}\fi\xspace \subseteq E$ of an oriented matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(\relax\ifmmode{E}\else{$E$}\fi\xspace, \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ is an inclusion-maximal subset of \relax\ifmmode{E}\else{$E$}\fi\xspace such that \relax\ifmmode{B}\else{$B$}\fi\xspace contains no circuit. The \emph{rank} of an oriented matroid is the size of its bases. An oriented matroid is called \emph{uniform}, if all subsets of $E$ with cardinality equal to the rank of the oriented matroid are bases.

The \emph{cocircuits} $\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace^*$ of an oriented matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ are the circuits of the \emph{dual} oriented matroid~$\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace^*$. To understand duality, we need the following notion of orthogonality:
\begin{definition}
    Two signed sets $X,Y$ are said to be \emph{orthogonal}, if  $\support{X}\cap \support{Y}=\emptyset$, or there exist $e,f\in\support{X}\cap\support{Y}$, such that $X_eY_e=-X_fY_f$.
\end{definition}
In other words, two signed sets are orthogonal if their supports either do not intersect at all, or if they agree (same non-zero sign) and disagree (opposite non-zero sign) on at least one element.
\begin{lemma}[\cite{bjoerner1999orientedmatroids}]\label[lemma]{lem:orthogonal}
    Let $X\in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$ be a circuit and $Y\in\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace^*$ be a cocircuit of some oriented matroid~$\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$. Then, $X$ and $Y$ are orthogonal.
\end{lemma}
 Given the set of circuits, the set of cocircuits can be computed, since the cocircuits are exactly the inclusion-minimal non-empty signed sets that are orthogonal to all circuits. Since duality of oriented matroids is self-inverse, the opposite holds too.

\begin{definition}
    In an oriented matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E,\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$, given a basis $B$ and an element $e\not\in B$, the \emph{fundamental circuit} $C(B,e)$ is the unique circuit $\relax\ifmmode{X}\else{$X$}\fi\xspace$ with $\relax\ifmmode{X}\else{$X$}\fi\xspace_e = +$ and $\support{\relax\ifmmode{X}\else{$X$}\fi\xspace}\subseteq \relax\ifmmode{B}\else{$B$}\fi\xspace \cup \{e \}$.
\end{definition}
\begin{definition}\label[definition]{def:fundamentalCocircuit}
    In an oriented matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E,\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$, given a basis $B$ and an element $e\in B$, the \emph{fundamental cocircuit} $C^*(B,e)$ is the unique cocircuit $D$ with $D_e=+$ and  $\support{D}\cap (B\setminus\{e\})=\emptyset$.
\end{definition}



An oriented matroid $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace=(E\cup\{q\},\f{\widehat{\mathcal{C}}}\xspace)$ is called an \emph{extension of }$\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$, if its \emph{minor}
$\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace\setminus \relax\ifmmode{q}\else{$q$}\fi\xspace := (\relax\ifmmode{E}\else{$E$}\fi\xspace, \{\relax\ifmmode{X}\else{$X$}\fi\xspace \mid \relax\ifmmode{X}\else{$X$}\fi\xspace \in \f{\widehat{\mathcal{C}}}\xspace \text{ and }\relax\ifmmode{X}\else{$X$}\fi\xspace_\relax\ifmmode{q}\else{$q$}\fi\xspace = 0 \} )$ is equal to $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$.
A \emph{localization} is a way to describe an extension $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace=(\relax\ifmmode{E}\else{$E$}\fi\xspace\cup\{q\},\f{\widehat{\mathcal{C}}}\xspace)$ of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E,\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$.
\begin{definition}\label[definition]{def:localization}
    Given an oriented matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ on ground set $E$ and with cocircuits $\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace^*$, a function $\sigma:\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace^*\rightarrow\{-,0,+\}$ defines the following family of signed sets
    \begin{align*}
\begin{split}
\f{\widehat{\mathcal{C}}}\xspace^*:=&\{(Y,\:\sigma(Y)):Y\in\mathcal{C}^*\}\:\cup\\
&\{(Y_1\circ Y_2,\:0):Y_1,Y_2\in\mathcal{C}^*, \text{ for adjacent }Y_1,Y_2\text{ with}\\
&\;\;\sigma(Y_1)=-\sigma(Y_2)\not=0\},
\end{split}
\end{align*}
    where the notation $(X,s)$ denotes the signed set where all elements of $E$ have the same sign as in $X$, and the new element $q$ gets sign $s$. For the definition of adjacency, we refer the reader to \cite{bjoerner1999orientedmatroids}. For the further discussion, only the first of the two sets forming $\f{\widehat{\mathcal{C}}}\xspace^*$ is relevant.
    
    The function $\sigma$ is called a \emph{localization}, if $\f{\widehat{\mathcal{C}}}\xspace^*$ is a valid set of cocircuits. Then, the oriented matroid $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ on the ground set $E\cup\{q\}$ with cocircuits $\f{\widehat{\mathcal{C}}}\xspace^*$ is called the \emph{extension of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ specified by $\sigma$}.
\end{definition}


\subsection{\texorpdfstring{\gls*{POMCP}\xspace}{P-OMCP}}
We consider oriented matroids $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E_{2n}, \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ on the ground set $E_{2n}=S\cup T$, which is made up of two parts $S=\{s_1,\ldots,s_n\}$ and $T=\{t_1,\ldots,t_n\}$, $S\cap T=\emptyset$. We call a set $J\subseteq E_{2n}$ \emph{complementary}, if it contains no \emph{complementary pair} $s_i,t_i$.


\begin{definition}[P-matroid]\label[definition]{def:Pmatroid}
An oriented matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E_{2n},\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ is a \emph{P-matroid} if \relax\ifmmode{S}\else{$S$}\fi\xspace is a basis and there is no \emph{sign-reversing circuit}. A sign-reversing circuit is a circuit $\relax\ifmmode{X}\else{$X$}\fi\xspace$ such that for each complementary pair $s_i,t_i$ contained in $\support{\relax\ifmmode{X}\else{$X$}\fi\xspace}$, 
$\relax\ifmmode{X}\else{$X$}\fi\xspace_{\relax\ifmmode{s}\else{$s$}\fi\xspace_i} = -\relax\ifmmode{X}\else{$X$}\fi\xspace_{\relax\ifmmode{t}\else{$t$}\fi\xspace_i}$.
\end{definition}

\begin{example}
\label[example]{ex:PMatroid}

The matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(\{s,t\},\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ is a P-Matroid. The matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace'=(\{s,t\},\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace')$ is \emph{not} a P-Matroid, since both of its circuits are sign-reversing.
\begin{align*}
\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace= \{\begin{pmatrix}+& +\end{pmatrix}, \begin{pmatrix}-& -\end{pmatrix} \}, \qquad \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace'=  \{\begin{pmatrix}+& -\end{pmatrix}, \begin{pmatrix}-& +\end{pmatrix} \}.
\end{align*}
\end{example}


Let \relax\ifmmode{q}\else{$q$}\fi\xspace be such that $\relax\ifmmode{q}\else{$q$}\fi\xspace \notin \relax\ifmmode{E}\else{$E$}\fi\xspace_{2\relax\ifmmode{n}\else{$n$}\fi\xspace}$.
Then $\f{\widehat{\GroundSet_{2\length}}}\xspace \coloneqq \relax\ifmmode{S}\else{$S$}\fi\xspace \cup \relax\ifmmode{T}\else{$T$}\fi\xspace \cup \{\relax\ifmmode{q}\else{$q$}\fi\xspace \}$, and we write $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace = (\f{\widehat{\GroundSet_{2\length}}}\xspace, \f{\widehat{\mathcal{C}}}\xspace)$ for an \emph{extension of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$}.

\begin{example}\label[example]{ex:PMatroidExtension}
$\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace=(\{s,t,q\}, \f{\widehat{\mathcal{C}}}\xspace)$ and  $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace'=(\{s,t,q\}, \f{\widehat{\mathcal{C}}}\xspace')$ are both valid extensions of the P-Matroid \relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace from \Cref{ex:PMatroid} for \f{\widehat{\mathcal{C}}}\xspace and $\f{\widehat{\mathcal{C}}}\xspace'$ as given below.
\Cref{fig:realizationOfPME,fig:realizationOfPMED} show the realizations of the corresponding oriented matroids as arrangements of oriented hyperplanes through the origin; each one-dimensional cell of these arrangements corresponds to a circuit.

\begin{figure}[h!]
\begin{minipage}{0.65\textwidth}
\begin{tikzpicture}[scale = 0.8]
\small
\filldraw[red!10] (-4,-2) -- (4,2) -- (4,3) -- (-4, 3) -- cycle;
\filldraw[black] (0,0) circle (2pt);
\node at (0, -0.5) {000};
\hyperplane{s}{(-2,2)}{(2,-2)}
\hyperplane{t}{(-2.5,0.5)}{(3,-0.5)}
\hyperplane{q}{(-3,-1.5)}{(3,1.5)}
\filldraw[red] (-2.4,2.4) circle (2pt) node[anchor=east]{$\begin{pmatrix}0 & + & +\end{pmatrix}$};
\filldraw[] (2.4,-2.4) circle (2pt) node[anchor=north east]{$\begin{pmatrix}0 & - & -\end{pmatrix}$};
\filldraw[red] (-3,0.6) circle (2pt) node[anchor=north east]{$\begin{pmatrix}- & 0 & +\end{pmatrix}$};
\filldraw[] (3,-0.5) circle (2pt) node[anchor=north]{$\begin{pmatrix}+ & 0 & -\end{pmatrix}$};
\filldraw[] (-3.5,-1.75) circle (2pt) node[anchor=north west]{$\begin{pmatrix}- & - & 0\end{pmatrix}$};
\filldraw[] (3,1.5) circle (2pt) node[anchor=south east]{$\begin{pmatrix}+ & + & 0\end{pmatrix}$};
\end{tikzpicture}
\end{minipage} \hfill
\begin{minipage}{0.34\textwidth}
\begin{align*}
\f{\widehat{\mathcal{C}}}\xspace= \{\begin{pmatrix}+& +& 0\end{pmatrix},\\\begin{pmatrix}-& -& 0\end{pmatrix},\\\begin{pmatrix} +& 0& -\end{pmatrix},\\\begin{pmatrix}-& 0& +\end{pmatrix},\\\begin{pmatrix} 0& +& +\end{pmatrix},\\\begin{pmatrix}0& -& -\end{pmatrix}\}
\end{align*}
\end{minipage}
\caption{Realization of \relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace.}
\label{fig:realizationOfPME}
\end{figure}


\begin{figure}[h!]
\begin{minipage}{0.65\textwidth}
\begin{tikzpicture}[scale = 0.8]
\small
\filldraw[red!10] (-4,-2) -- (4,2) -- (4,4) -- (-4, 4) -- cycle;
\filldraw[black] (0,0) circle (2pt);
\node at (0, -0.5) {000};
\hyperplane{s and t}{(-2.5,0.5)}{(3,-0.5)}
\hyperplane{q}{(-3,-1.5)}{(3,1.5)}
\filldraw[red] (-3,0.6) circle (2pt) node[anchor=north east]{$\begin{pmatrix}0 & 0 & +\end{pmatrix}$};
\filldraw[] (3,-0.5) circle (2pt) node[anchor=south west]{$\begin{pmatrix}0 & 0 & -\end{pmatrix}$};
\filldraw[] (-3.5,-1.75) circle (2pt) node[anchor=north west]{$\begin{pmatrix}- & - & 0\end{pmatrix}$};
\filldraw[] (3,1.5) circle (2pt) node[anchor=south east]{$\begin{pmatrix}+ & + & 0\end{pmatrix}$};
\end{tikzpicture}
\end{minipage}\hfill
\begin{minipage}{0.34\textwidth}
\begin{align*}
\f{\widehat{\mathcal{C}}}\xspace= \{\begin{pmatrix}+& +& 0\end{pmatrix},\\\begin{pmatrix}-& -& 0 \end{pmatrix},\\\begin{pmatrix} 0& 0& + \end{pmatrix},\\\begin{pmatrix} 0& 0& -\end{pmatrix}\}
\end{align*}
\end{minipage}
\caption{Realization of $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace'$.}
\label{fig:realizationOfPMED}
\end{figure}
\end{example}

Given an extension  $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace = (\f{\widehat{\GroundSet_{2\length}}}\xspace, \f{\widehat{\mathcal{C}}}\xspace)$ of a P-matroid, the goal of the \emph{P-Matroid Oriented Matroid Complementarity Problem (P-OMCP)} is to find a circuit $\relax\ifmmode{X}\else{$X$}\fi\xspace \in \f{\widehat{\mathcal{C}}}\xspace$ with 
$\relax\ifmmode{X}\else{$X$}\fi\xspace \geq 0$,
$\relax\ifmmode{X}\else{$X$}\fi\xspace_\relax\ifmmode{q}\else{$q$}\fi\xspace = +$, and
$\relax\ifmmode{X}\else{$X$}\fi\xspace_{s_i} \relax\ifmmode{X}\else{$X$}\fi\xspace_{t_i} = 0$ for every $i \in [n]$.
The matroid extension is given to an algorithm by a circuit oracle, which given a set $B\subset \f{\widehat{\GroundSet_{2\length}}}\xspace$ and another element $e\in\f{\widehat{\GroundSet_{2\length}}}\xspace\setminus B$ either returns that $B$ is not a basis of $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$, or returns the fundamental circuit $C(B,e)$ (recall that this is the unique circuit $\relax\ifmmode{X}\else{$X$}\fi\xspace \in \f{\widehat{\mathcal{C}}}\xspace$ with $\relax\ifmmode{X}\else{$X$}\fi\xspace_e = +$ and $\support{\relax\ifmmode{X}\else{$X$}\fi\xspace}\subseteq \relax\ifmmode{B}\else{$B$}\fi\xspace \cup \{e \}$). It is known that in P-matroids and P-matroid extensions, every complementary set $B\subset S\cup T$ of size $n$ is a basis~\cite{klaus2012phd}.
Every P-OMCP instance has a unique solution~\cite{todd1984matroids}.
The unique solution of an \gls*{POMCP}\xspace instance with \relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace of \Cref{ex:PMatroidExtension} as input is $\begin{pmatrix}0&+&+\end{pmatrix}$, the unique solution in $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace'$ is  $\begin{pmatrix}0&0&+\end{pmatrix}$.



A P-matroid extension (a P-OMCP instance) is \emph{non-degenerate}, if for every complementary basis $B$, the circuit $C(B,q)$ is non-zero on all elements in $B\cup\{q\}$. 

\begin{example}
The red shaded area in \Cref{fig:realizationOfPME,fig:realizationOfPMED} denotes the areas where $q$ is positive. The circuits marked in red are the fundamental circuits $C(\{s\},q)$ and $C(\{t\},q)$. As can be seen, the P-Matroid extension \relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace in \Cref{ex:PMatroidExtension} is non-degenerate, whereas $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace'$ is degenerate.
\end{example}



\subsection{Unique Sink Orientation (USO)}

The \emph{$n$-dimensional hypercube graph} $Q_n$ (\emph{$n$-cube}) is the undirected graph on the vertex set \mbox{$V(Q_n) = \{0,1\}^n$}, where two vertices are connected by an edge if they differ in exactly one coordinate. 
An \emph{orientation} $O: V(Q_n) \rightarrow \{-,+\}^n$ assigns each vertex an orientation of its incident edges, where $O(v)_i=+$ denotes an outgoing edge from vertex $v$ in dimension $i$ and $O(v)_i=-$ denotes an incoming edge.
A \emph{Unique Sink Orientation (USO)} is an orientation, such that every non-empty subcube contains exactly one sink, i.e., a unique vertex $v$ with $O(v)_i=-$ for all dimensions $i$ in the subcube~\cite{szabo2001usos}.

\begin{lemma}[Szab{\'o}{}-Welzl Condition \cite{szabo2001usos}]\label[lemma]{lem:szabowelzl}
An orientation $O$ of $Q_n$ is USO if and only if for all pairs of distinct vertices $v,w\in V(Q_n)$, we have:
$\exists i\in [n]:\; (\relax\ifmmode{v}\else{$v$}\fi\xspace_i \not= \relax\ifmmode{w}\else{$w$}\fi\xspace_i) \wedge (O(\relax\ifmmode{v}\else{$v$}\fi\xspace)_i \not= O(\relax\ifmmode{w}\else{$w$}\fi\xspace)_i)$.
\end{lemma}

The classical algorithmic problem associated to USOs is that of finding the unique global sink $v$ with $\forall i:O(v)_i=-$, with as few as possible queries to an oracle computing $O$.

\subsection{Classical Reduction} \label{sec:ClassicReduction}

Todd~\cite{todd1984matroids} showed that a non-degenerate P-OMCP given by a matroid $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace = (\f{\widehat{\GroundSet_{2\length}}}\xspace, \f{\widehat{\mathcal{C}}}\xspace)$ can be translated to an USO of the $n$-cube. Every vertex $v$ of the cube is associated with a complementary basis $B(v)\subset S\cup T$. For each $i \in [n]$, $s_i\in B(v)$ if $v_i=0$, otherwise $t_i\in B(v)$. The orientation $O(v)$ is then computed using the fundamental circuit $C:=C(B(v),q)$:
\[
O(v)_i := \begin{cases}
+ & \text{if } C_{s_i} = - \text{ or } C_{t_i} = - ,\\
- & \text{if } C_{s_i} = + \text{ or } C_{t_i} = +.
\end{cases}
\]
As the P-OMCP instance is non-degenerate, no other case can occur.
Todd showed that the computed orientation $O$ is USO, and that its sink $v$
corresponds to a fundamental circuit $C(B(v),q)$ which is positive on all elements and thus a solution to the P-OMCP instance.

\begin{example}
Recall the P-Matroid extension \relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace from \Cref{ex:PMatroidExtension}. \Cref{fig:USO_of_ExtendedMatroid} shows the USO created by this reduction, where $B(0)=s$ and $B(1)=t$.

\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=1.5, roundnode/.style={circle, draw= black, thick, minimum size=7mm}]
\node[roundnode] (S) at (0,0) {$0$};
\node at (-0.5,0.5) {$C(B(0), q) = \begin{pmatrix} \textcolor{red}{-} & 0 & + \end{pmatrix}$};
\node[roundnode] (T) at (2,0) {$1$};
\node at (2.5,0.5) {$C(B(1), q) = \begin{pmatrix}0 & \textcolor{red}{+} & + \end{pmatrix}$};

\draw (S) -- (T) 
node[currarrow,pos=0.25,xscale=1,sloped] {} 
node[currarrow,pos=0.75,xscale=1,sloped] {};
\end{tikzpicture}
\caption{USO created by the reduction from \relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace.}
\label{fig:USO_of_ExtendedMatroid}
\end{figure}
\end{example}


\section{The Effect of Degeneracy on the Resulting USOs}\label[section]{sec:structural}
In the above reduction, if the P-OMCP instance is degenerate, we can sometimes not decide which way to orient an edge since $C_{s_i}=C_{t_i}=0$. For now, we leave these edges unoriented.
This leads to a \emph{partial orientation} of the hypercube, which is a function $O: V(Q_k) \rightarrow \{-,0,+\}^k$ where~$O(v)_i=0$ denotes an unoriented edge. We call such a partial orientation arising from a degenerate P\nobreakdash-OMCP a \emph{partial P-matroid USO (PPU)}.
In this section we aim to understand the structure of unoriented edges in PPUs.

Not every partial orientation can be turned into an USO by directing the unoriented edges. We thus state the following condition inspired by the Szab{\'o}{}-Welzl condition:
\begin{definition}\label[definition]{def:partialSW}
    A partial orientation $O$ is said to be \emph{partially Szab{\'o}{}-Welzl} if for any two distinct vertices $v,w\in V(Q_k)$, either
    \begin{gather}
    O(v)_i=O(w)_i=0 \text{ for all }i \text{ with }v_i\not=w_i,\text{ or}\\
    \exists i : v_i\not=w_i \wedge \big((O(v)_i=+ \wedge O(w)_i=-)\vee (O(v)_i=-\wedge O(w)_i=+)\big).
    \end{gather}
\end{definition}

\begin{lemma}\label[lemma]{lem:completable}
    A partial orientation $O$ which is partially Szab{\'o}{}-Welzl can be extended to an USO by orienting all unoriented edges towards the endpoint with fewer $1$s, i.e., downwards.
\end{lemma}
\begin{proof}
    By orienting all unoriented edges of $O$ from the vertex with more $1$s to the vertex with fewer $1$s (i.e., ``downwards''), any two vertices that previously fulfilled condition (1) of \Cref{def:partialSW} now fulfill the classic Szab{\'o}{}-Welzl condition as in \Cref{lem:szabowelzl}. Note that condition (2) of \Cref{def:partialSW} is equivalent to this classic condition on full (non-partial) orientations. We conclude that all pairs of vertices must now fulfill the Szab{\'o}{}-Welzl condition as in \Cref{lem:szabowelzl}.
\end{proof}

\begin{lemma}\label[lemma]{lem:pmatroidszabowelzl}
    A partial P-matroid USO is partially Szab{\'o}{}-Welzl.
\end{lemma}
\begin{proof}
    Assume two vertices $v,w$ in a PPU $O$ failed both conditions of \Cref{def:partialSW}. Let $V=C(B(v),q)$ and $W=C(B(w),q)$ be the fundamental circuits used to derive $O(v)$ and $O(w)$. Since $v$ and $w$ violate the first condition of \Cref{def:partialSW}, $V\not=W$. Applying circuit axiom (C3) to $V$ and $-W$ to eliminate the element $q$ shows that there exists a circuit $Z$ with certain properties. Since $q\not\in\support{Z}$, $Z$ must contain both $s_i$ and $t_i$ for at least one $i\in [k]$ (since all complementary sets are independent in a P-matroid extension). As we assumed that $v$ and $w$ violate the second condition of \Cref{def:partialSW}, we know that $s_i$ and $t_i$ must have opposite signs in $Z$. Since this holds for any $i\in [k]$, $Z$ is a sign-reversing circuit of the underlying P-matroid, which contradicts \Cref{def:Pmatroid}. We conclude that no two vertices can fail \Cref{def:partialSW}.
\end{proof}

\begin{lemma}\label[lemma]{lem:unorientedsubcubes}
    In a partial P-matroid USO, the unoriented edges form a set of vertex-disjoint faces. In each such face, the orientation is the same at every vertex.
\end{lemma}
\begin{proof}
    Let $v$ be a vertex of a PPU, and let $w$ be another vertex within the face spanned by the unoriented edges incident to $v$. Then, the fundamental circuit $C(B(v),q)$ fulfills all the conditions that a circuit has to fulfill to be the fundamental circuit $C(B(w),q)$. Since fundamental circuits are unique in all oriented matroids~\cite{klaus2012phd}, we must have $C(B(v),q)=C(B(w),q)$ and thus $v$ and $w$ must be oriented the same way, which implies the lemma.
\end{proof}

\Cref{lem:completable,lem:pmatroidszabowelzl,lem:unorientedsubcubes}, and \cite[Corollary 6]{schurr2004quadraticbound} imply that the unoriented subcubes of a PPU can in fact be oriented according to \emph{any} USO:

\begin{corollary} \label[corollary]{cor:CompleteUSOArbitrarily}
Let $O$ be a PPU and let $O'$ be the orientation obtained by independently orienting each unoriented face $f$ of $O$ according to some USO of the same dimension as $f$. Then, $O'$ is USO.
\end{corollary}
\begin{proof}
    By \Cref{lem:pmatroidszabowelzl,lem:completable}, $O$ can be extended to some USO. By \Cref{lem:unorientedsubcubes}, each unoriented face is a hypervertex; a face where all edges of the same dimension leaving the face are oriented the same way. By \cite[Corollary 6]{schurr2004quadraticbound}, each such hypervertex can be reoriented according to an arbitrary USO while preserving that the whole orientation is USO.
\end{proof}

\begin{example}
Recall the P-Matroid extension \relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace from \Cref{ex:PMatroidExtension}. \Cref{fig:USO_of_ExtendedMatroidDegenerate} shows the USO created by this reduction, where $B(0)=s$ and $B(1)=t$.

\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=1.5, roundnode/.style={circle, draw= black, thick, minimum size=7mm}]
\node[roundnode] (S) at (0,0) {$0$};
\node at (-0.5,0.5) {$C(B(0), q) = \begin{pmatrix}\textcolor{red}{0} & 0 & + \end{pmatrix}$};
\node[roundnode] (T) at (2,0) {$1$};
\node at (2.5,0.5) {$C(B(1), q) = \begin{pmatrix}0 & \textcolor{red}{0} & + \end{pmatrix}$};
\draw (S) -- (T);
\end{tikzpicture}
\caption{USO created by the reduction from the degenerate P-Matroid extension $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace'$.}
\label[figure]{fig:USO_of_ExtendedMatroidDegenerate}
\end{figure}
\end{example}


\section{Constructions Based on Degeneracy and Perturbations}\label{sec:constructions}
In this section we show how existing constructions of oriented matroid extensions can be interpreted as constructions of (partial) P-matroid USOs.
An extension $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ of an oriented matroid $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ can be uniquely described by a \emph{localization}, a function $\sigma$ from the set $\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace^*$ of cocircuits of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ to the set $\{-,0,+\}$. We give some more background about localizations in \Cref{sec:OMPrelims}. Note that not every function $f:\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace^*\rightarrow\{-,0,+\}$ describes a valid extension and thus not every such function is a localization.
The following lemma connects a localization to the circuits relevant to the resulting (partial) P-matroid USO.

\begin{lemma}\label[lemma]{lem:localizationsAndOrientations}
    Let $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ be a P-matroid and let $\sigma$ be a localization for $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ describing the extension~$\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$. Then, for any complementary basis $B$ of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ (and thus also of $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$), and every element $e\in B$, the sign of $e$ in the fundamental circuit $C(B,q)$ of $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ is the opposite of the sign assigned by $\sigma$ to the fundamental cocircuit $C^*(B,e)$ of  $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$.
\end{lemma}
\begin{proof}
    $D:=C^*(B,e)$ is a cocircuit of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$. By \Cref{def:localization}, $\widehat{D}:=(D,\sigma(D))$ must be a cocircuit of $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$.
    
    By \Cref{def:fundamentalCocircuit}, $\support{\widehat{D}}$ must be a subset of $\f{\widehat{\GroundSet_{2\length}}}\xspace\setminus (B\setminus\{e\})$ and $
    \widehat{D}_e=+$. On the other hand, the support of $C:=C(B,q)$ must be a subset of $B\cup\{q\}$, and $C_q=+$.

    \Cref{lem:orthogonal} says that $C$ and $\widehat{D}$ must be orthogonal, i.e., their supports either do not intersect, or they must agree and disagree on at least one element. Since $\support{C}\cap\support{\widehat{D}}\subseteq\{e,q\}$, the first case only occurs if $C_e=\widehat{D}_q=0$. The second case can only occur if $C_e=-\widehat{D}_q$, since $C_q=\widehat{D}_e=+$.
\end{proof}

Las Vergnas~\cite{lasvergnas1978extensions} showed that the set of localizations is closed under composition, i.e., given two localizations $\sigma_1,\sigma_2$, the following function is a localization too:
\[\forall c\in\mathcal{C}^*: (\sigma_1\circ \sigma_2)(c):=\begin{cases}
\sigma_1(c), & \text{if $\sigma_1(c)\not=0$},\\
\sigma_2(c), & \text{otherwise.}
\end{cases}\]


\Cref{lem:localizationsAndOrientations} allows us to understand the effect of such composition on the resulting (partial) P-matroid USO: For localizations $\sigma_1,\sigma_2$ and their corresponding PPUs $O_1,O_2$, the PPU $O'$ given by the localization $\sigma_1\circ\sigma_2$ is
\[\forall v\in V(Q_k), i\in [k]: O'(v)_i=\begin{cases}
O_1(v)_i, & \text{if } O_1(v)_i\not=0,\\
O_2(v)_i, & \text{otherwise.}
\end{cases}
\]
This can be seen as filling in all unoriented subcubes of $O_1$ with the orientation $O_2$.

Furthermore, Las Vergnas~\cite{lasvergnas1978extensions} describes \emph{lexicographic extensions} of oriented matroids.

\begin{definition}[Lexicographic extension~\cite{lasvergnas1978extensions}]\label[definition]{def:lexicographic}
    Let $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E,\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ be an oriented matroid. Given an element $e\in E$ and a sign $s\in\{-,0,+\}$, the function $\sigma:\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace^*\rightarrow\{-,0,+\}$ given by
    \[\sigma(D):=\begin{cases}
    s\cdot D_e, & \text{ if } D_e\not=0,\\
    0, & \text{ otherwise,}
    \end{cases}
    \]
    is a localization. The extension of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ specified by this localization is called the \emph{lexicographic extension} of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ by $[s\cdot e]$.
\end{definition}

Lexicographic extensions of \emph{uniform} P-matroids give rise to PPUs in which all edges of some dimension are oriented the same way, and one half is left unoriented while the other half is completely oriented (see \Cref{fig:lexicographicextension}).

\begin{figure}
    \centering
    \includegraphics{figs/lexicographicextension.pdf}
    \caption{The form of the PPU given by a lexicographic extension of a uniform P-matroid.}
    \label{fig:lexicographicextension}
\end{figure}

\begin{lemma}\label[lemma]{lem:lexicographicextensions}
    Let $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E_{2n},\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ be a P-matroid. Let $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ be the lexicographic extension of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ by $[+\cdot t_i]$. Then, in the partial P-matroid USO $O$ defined by $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$, the upper $i$-facet (the facet of vertices $v$ with $v_i=1$) is an unoriented subcube, and all $i$-edges point towards this facet. Furthermore, if $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ is uniform, the lower $i$-facet is completely oriented.
\end{lemma}
\begin{proof}
    We first prove that all edges in dimension $i$ are oriented from the vertices with $v_i=0$ to the vertices with $v_i=1$.
    As $t_i$ is positive in all cocircuits $C^*(B,t_i)$ for $B$ such that $t_i\in B$, $\sigma$ assigns $+$ to all such cocircuits. By \Cref{lem:localizationsAndOrientations}, for each vertex $v$ with $v_i=1$, we have $O(v)_i=-$.
    
    Furthermore, since $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ is a P-matroid, every complementary set of $n$ elements is a basis; thus, also every such set is a cobasis. We therefore know that every fundamental cocircuit $C^*(B,e)$ for a complementary set $B$ must be non-zero on both elements of the complementary pair which includes $e$.
    
    For any basis $B$ with $s_i\in B$, $t_i$ is thus non-zero in $C^*(B,s_i)$, and $\sigma$ assigns a non-zero sign to this cocircuit. By \cite[Theorem 5.4]{klaus2012phd}, a P-matroid contains no \emph{sign-preserving} cocircuit, so $s_i$ and $t_i$ must have opposite signs in this cocircuit. Thus, $t_i$ must be negative in $C^*(B,s_i)$, and $\sigma$ assigns $-$ to it. We conclude that for each vertex $v$ with $v_i=0$, we have $O(v)_i=+$.

    Next, we prove that the facet of vertices $v$ with $v_i=1$ is unoriented. Let $B$ be a basis with $t_i\in B$, and let $e\in B\setminus\{t_i\}$ be some element. Now, note that $t_i\not\in\support{C^*(B,e)}$. Thus, $\sigma$ assigns $0$ to these circuits, and therefore $C(B,q)_e=0$, showing that this facet is unoriented.

    Lastly, we prove that if $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ is uniform, the facet of vertices $v$ with $v_i=0$ is completely oriented. When $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ is uniform, all subsets $B\subset E$ of size $n$ are bases and cobases. Thus, $|\support{C^*(B,e)}|=n+1$, and for every complementary $B$ such that $s_i\in B$ and any $e\in B$, we have that $t_i\in\support{C^*(B,e)}$ and therefore $\sigma$ assigns a non-zero sign to that circuit. This shows that $|\support{C(B,q)}|=n+1$ too, proving that all edges around a vertex $v$ with $v_i=0$ are oriented. 
\end{proof}
Of course this lemma symmetrically also applies to lexicographic extensions where~$s=-$ or $e=s_i$. Switching $t_i$ out for $s_i$ swaps the role of the two facets, and switching the sign makes all $i$-edges point to the oriented facet instead of the unoriented one.

We can use these two construction techniques to prove a lower bound on the number of queries needed by deterministic sink-finding algorithms on P-matroid USOs. In essence, we successively build a localization by composition with lexicographic extensions. The construction keeps the invariant that there exists an unoriented subcube guaranteed to contain the global sink. The dimension of this subcube is reduced by at most one with every query, thus at least $n$ queries are required.

\begin{theorem}\label[theorem]{thm:lowerbound}
Let $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace=(E_{2n},\relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace)$ be a uniform P-matroid. Then, for every deterministic sink-finding algorithm $\mathcal{A}$, there exists a non-degenerate extension $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ of $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$ such that $\mathcal{A}$ requires at least $n$ queries to find the sink of the P-matroid USO given by $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$.
\end{theorem}
\begin{proof}
We specify an adversarial procedure which iteratively builds up a localization $\sigma$ for $\relax\ifmmode{{\mathcal{M}}}\else{${\mathcal{M}}$}\fi\xspace$. At any point of this procedure, the current localization describes an extension $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ for which the PPU $O$ contains exactly one unoriented subcube $U$, and all edges incident to $U$ are oriented into $U$. Thus, the global sink of $O$ must lie in $U$, but its exact location has not been determined yet.

At the beginning of the procedure, $\sigma$ is set to be all-zero, i.e., $O$ is completely unoriented and $U$ is the whole cube. Now, whenever the sink-finding algorithm queries a vertex $v$, the adversarial procedure must return the complete orientation around this vertex. If $v$ lies outside of $U$, it is already completely oriented, and its orientation can simply be returned. Otherwise, if $v$ lies in $U$, the localization $\sigma$ has to be changed. To do this, we pick one dimension $i$ which spans $U$. If $v_i=0$, we change $\sigma$ to $\sigma' := \sigma \circ [+\cdot t_i]$, i.e., $\sigma$ is combined with the lexicographic extension $[+\cdot t_i]$. On $O$ this has the effect that some edges in $U$ are oriented. By \Cref{lem:lexicographicextensions}, all edges in the lower $i$-facet of $U$ are oriented, and all $i$-edges in $U$ are pointed away from this facet. Thus, $v$ is now completely oriented, and $U$ has shrunk by one dimension. The orientation of $v$ can thus be returned.

Note that if $v_i=1$, the lexicographic extension would be picked to be $[+\cdot s_i]$, the rest of the procedure staying the same.

Since $U$ shrinks by only one dimension with every query, and $U$ has $n$ dimensions at the beginning, the first $n$ vertices queried by the algorithm are never the sink. Thus, it takes at least $n$ queries to determine the sink.
\end{proof}

Previously, the best known lower bound for sink-finding on P-matroid USOs was $\Omega(\log n)$ queries~\cite{weber2022matousekgap}. In contrast, the stronger, almost-quadratic lower bound of Schurr and Szab{\'o}{}~\cite{schurr2004quadraticbound} does not apply to P-matroid USOs (for a proof of this see \Cref{lem:schurrnonpmatroid} in \Cref{sec:SchurrSzaboNonHoltKlee}).

The P-Matrix Linear Complementarity Problem (P-LCP) is an algebraic analogue of P\nobreakdash-OMCP. We discuss our results (\Cref{sec:structural,sec:constructions}) in the context of P-LCPs in \Cref{sec:PLCP}.

\section{The Search Problem Complexity of \texorpdfstring{\gls*{POMCP}\xspace}{P-OMCP}}\label{sec:searchcomplexity}

An instance of \UniqueEndOfPotentialLine consists of an implicitly given exponentially large graph \Graph, in which each vertex has a positive cost and in- and out-degree at most one.
Thus, the graph is a collection of directed paths called \emph{lines}.
The computational task is as follows: if the nodes of \Graph form a single line (that starts in some given start vertex) with strictly increasing cost, then find the unique end node of this line --- a \emph{sink}. 
Otherwise, either find \emph{some} sink in \Graph 
or a \emph{violation certificate} that shows that \Graph does not consist of a single line. 
\UniqueEndOfPotentialLine is a total search problem, i.e., there always exists a sink or a violation. 
Note that there might exist a sink and a violation simultaneously.

\begin{definition}
The search complexity class \UEOPL contains all problems that can be reduced in polynomial time to \myProblem{Unique End of Potential Line}. 
Thus, the complexity class \UEOPL captures all total search problems where the space of candidate solutions has the structure of a unique line with increasing cost.
\end{definition}


\UEOPL was introduced in 2018 by Fearnley et al. \cite{UEOPL2020}.
\UEOPL is a subclass of \f{\Class{PPAD} \cap \Class{PLS}} \cite{CLSIsPPADPLS}.
Problems in \UEOPL are not known to be solvable in polynomial time.

The promise version of a total search problem with violations is to find a solution under the promise that no violations exist for the given instance.
\Class{PromiseUEOPL}\xspace is the promise version of the search problem class \UEOPL.


A search problem reduction from a problem \f{\searchProblem}\xspace to a problem \f{T}\xspace is \emph{promise preserving}, 
if every violation of \f{T}\xspace is mapped back to a violation of \f{\searchProblem}\xspace
and every valid solution of \f{T}\xspace is mapped back to a valid solution or a violation of \f{\searchProblem}\xspace.
Promise preserving reductions are transitive.
When containment of a search problem \f{R}\xspace in \UEOPL is shown via a polynomial time, promise preserving reduction, the promise version of \f{R}\xspace is contained in \Class{PromiseUEOPL}\xspace.

We now state the problem of USO sink-finding as a total search problem with a violation.


\begin{definition}
Given an orientation function \f{\relax\ifmmode{O}\else{$O$}\fi\xspace: \{0, 1\}^\relax\ifmmode{n}\else{$n$}\fi\xspace \rightarrow \{+, -\}^\relax\ifmmode{n}\else{$n$}\fi\xspace}, the task of the total search problem \USO is to find:

\begin{itemize}[leftmargin=1.2cm]
\item[\emph{(U1)}\xspace] A vertex \f{\relax\ifmmode{v}\else{$v$}\fi\xspace \in \{0, 1\}^\relax\ifmmode{n}\else{$n$}\fi\xspace} such that \f{\forall i\in[n]: \relax\ifmmode{O}\else{$O$}\fi\xspace(\relax\ifmmode{v}\else{$v$}\fi\xspace)_i = -}. The vertex \relax\ifmmode{v}\else{$v$}\fi\xspace is a sink.



\item[\emph{(UV1)}\xspace] Two distinct vertices \f{\relax\ifmmode{v}\else{$v$}\fi\xspace, \relax\ifmmode{w}\else{$w$}\fi\xspace \in \{0, 1\}^\relax\ifmmode{n}\else{$n$}\fi\xspace} with
$\forall i\in [\relax\ifmmode{n}\else{$n$}\fi\xspace]:\; (\relax\ifmmode{v}\else{$v$}\fi\xspace_i = \relax\ifmmode{w}\else{$w$}\fi\xspace_i) \vee (O(\relax\ifmmode{v}\else{$v$}\fi\xspace)_i = O(\relax\ifmmode{w}\else{$w$}\fi\xspace)_i)$.
The orientation \relax\ifmmode{O}\else{$O$}\fi\xspace does not fulfill the \szabo-Welzl condition\xspace and thus is not USO. 

\end{itemize}

\end{definition}

\begin{lemma}[\cite{UEOPL2020}]
\USO is in \UEOPL and its promise version is in \Class{PromiseUEOPL}\xspace.
\end{lemma}

Next, we define the \gls*{POMCP}\xspace problem as a total search problem 
with violations. 

\begin{definition}\label[definition]{def:TotalPOMCP}
Let  $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace = (\f{\widehat{\GroundSet_{2\length}}}\xspace, \f{\widehat{\mathcal{C}}}\xspace)$ be an oriented matroid with the set \relax\ifmmode{S}\else{$S$}\fi\xspace being a basis.
The task of the total search version of \gls*{POMCP}\xspace is to find one of the following:
\begin{itemize}[leftmargin=1.2cm]
\item[\emph{(M1)}\xspace] A circuit $\relax\ifmmode{X}\else{$X$}\fi\xspace \in \f{\widehat{\mathcal{C}}}\xspace$ such that
$\relax\ifmmode{X}\else{$X$}\fi\xspace \geq 0$,
$\relax\ifmmode{X}\else{$X$}\fi\xspace_\relax\ifmmode{q}\else{$q$}\fi\xspace = +$ and
$\forall i \in [n] : \relax\ifmmode{X}\else{$X$}\fi\xspace_{s_i} \relax\ifmmode{X}\else{$X$}\fi\xspace_{t_i} = 0.$

\item[\emph{(MV1)}\xspace] A circuit $\relax\ifmmode{Z}\else{$Z$}\fi\xspace \in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$ which is sign-reversing.

\item[\emph{(MV2)}\xspace] A complementary set $B \subset E_{2n}$ of size $n$ which is not a basis of \relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace.

\item[\emph{(MV3)}\xspace] Two distinct, complementary circuits $\relax\ifmmode{X}\else{$X$}\fi\xspace, \relax\ifmmode{Y}\else{$Y$}\fi\xspace \in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$ with $\relax\ifmmode{X}\else{$X$}\fi\xspace_q = \relax\ifmmode{Y}\else{$Y$}\fi\xspace_q = +$ and\\\mbox{$\forall i \in [n] : X_{s_i}Y_{t_i}=X_{t_i}Y_{s_i}=0$}, or $X_{s_i}=Y_{t_i}$ and $X_{t_i}=Y_{s_i}$.

\end{itemize}
\end{definition}

The definition of the violation \emph{(MV3)}\xspace may look unintuitive, but the following lemma shows that it correctly implies that $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ is not a P-matroid extension.

\begin{lemma}\label[lemma]{lem:VioImpliesNotPMatroid}
A violation of type \emph{(MV3)}\xspace implies that $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ is not a P-matroid extension.   
\end{lemma}
\begin{proof}

Suppose we are given such a violation, i.e., two distinct complementary circuits $\relax\ifmmode{X}\else{$X$}\fi\xspace, \relax\ifmmode{Y}\else{$Y$}\fi\xspace \in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$ with $\relax\ifmmode{X}\else{$X$}\fi\xspace_q = \relax\ifmmode{Y}\else{$Y$}\fi\xspace_q = +$ and $\forall i \in [n] : X_{s_i}Y_{t_i}=X_{t_i}Y_{s_i}=0$ or $X_{s_i}=Y_{t_i}$ and $X_{t_i}=Y_{s_i}$.


As $X,Y$ are distinct, $X\neq Y$. Since $X_q=Y_q=+$, it holds that $X\neq -Y$. We can thus apply circuit axiom (C3) on circuits $X$ and $-Y$ and element $q\in X^+\cap (-Y)^-$.
It follows that there must exist some circuit \relax\ifmmode{Z}\else{$Z$}\fi\xspace with: 
\begin{itemize}
	\item $\relax\ifmmode{Z}\else{$Z$}\fi\xspace^+ \subseteq X^+ \cup (-Y)^+ \setminus \{q\}$ and 
	\item $\relax\ifmmode{Z}\else{$Z$}\fi\xspace^- \subseteq X^- \cup (-Y)^- \setminus \{q\}$.
\end{itemize}
If $\support{Z}$ contained no complementary pair, it would be a complementary set. Any complementary set $B\supseteq\support{Z}$ of size $n$ can not be a basis, since $\support{Z}$ is a circuit. This is a violation of type \emph{(MV2)}\xspace and implies that $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ is not a P-matroid extension.

Otherwise, $\support{Z}$ must contain at least one complementary pair $s_i,t_i$. 
As $X$ and $Y$ are complementary, $s_i$ and $t_i$ are each only contained in one of the two circuits, w.l.o.g. $s_i\in\support{X}$ and $t_i\in\support{Y}$. Therefore, $s_i$ and $t_i$ are each only contained in one of the two sets \mbox{$X^+\cup (-Y)^+\setminus\{q\}$} and $X^-\cup(-Y)^-\setminus\{q\}$. Since $X_{s_i}=Y_{t_i}$, they are both in different sets, and thus $Z_{s_i}=-Z_{t_i}$.
Since this holds for every complementary pair in $\support{Z}$, we conclude that $Z$ is sign-reversing. Thus $Z$ is a violation of type \emph{(MV1)}\xspace, and $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ can not be a P-matroid extension.

Note that even if we cannot find \relax\ifmmode{Z}\else{$Z$}\fi\xspace explicitly in polynomial time, we can check the conditions on \relax\ifmmode{X}\else{$X$}\fi\xspace and \relax\ifmmode{Y}\else{$Y$}\fi\xspace in polynomial time.
\end{proof}

Technically, the violation \emph{(MV1)}\xspace would be enough to make this search problem total, but our reduction to \USO detects only violations of type \emph{(MV2)}\xspace and \emph{(MV3)}\xspace.
Note that as Fearnley et al. \cite{fearnley2020ueopl} already observed, there may be a difference in the complexity of a total search problem depending on the violations chosen. There is no trivial way known to the authors to transform a violation of type \emph{(MV3)}\xspace or \emph{(MV2)}\xspace to a violation of type \emph{(MV1)}\xspace.

With the help of \Cref{lem:completable,lem:pmatroidszabowelzl} we now adapt Todd's reduction of non-degenerate \gls*{POMCP}\xspace instances to USO (recall \Cref{sec:ClassicReduction})  to also work with degenerate instances and their respective total search versions.

Given a \gls*{POMCP}\xspace instance $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace = (\f{\widehat{\GroundSet_{2\length}}}\xspace, \f{\widehat{\mathcal{C}}}\xspace)$ (note that $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ is possibly not a P-matroid extension, or degenerate), we define the orientation $\relax\ifmmode{O}\else{$O$}\fi\xspace: V(Q_n) \rightarrow \{+, -\}^n$:
\[
\relax\ifmmode{O}\else{$O$}\fi\xspace(v)_i := \begin{cases}
- & \text{if } B(v) \text{ is not a basis}, \\
- & \text{if } v_i=0 \text{ and } \f{C}\xspace_{s_i} = 0, \\
+ & \text{if } v_i=1 \text{ and }\f{C}\xspace_{t_i} = 0 ,\\
+ & \text{if } v_i=0 \text{ and } \f{C}\xspace_{s_i} = - \\
  & \text{or } v_i=1 \text{ and }\f{C}\xspace_{t_i} = - ,\\
- & \text{otherwise,}
\end{cases}
\]
with $B(v)$ and $C:=C(B(v), q)$ defined as in \Cref{sec:ClassicReduction}.
Furthermore, using \Cref{lem:pmatroidszabowelzl,lem:completable} we know that $O$ is USO if $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace$ is a P-matroid extension.

\begin{theorem} \label{thm:ReductionIsPromisePreserving}
The construction above is a polynomial time, promise preserving reduction from \gls*{POMCP}\xspace to \USO.
\end{theorem}
\begin{proof}
Given a \gls*{POMCP}\xspace instance $\relax\ifmmode{\widehat{\mathcal{M}}}\else{$\widehat{\mathcal{M}}$}\fi\xspace = (\f{\widehat{\GroundSet_{2\length}}}\xspace, \f{\widehat{\mathcal{C}}}\xspace)$, let $(Q_n, O)$ be an \USO instance with \relax\ifmmode{O}\else{$O$}\fi\xspace as defined above.

\subparagraph*{Polynomial time}
For the reduction we build an orientation oracle $O$ for \USO from the given circuit oracle for \gls*{POMCP}\xspace. Note that this does not mean that we have to compute the output of $O$ for every vertex, we simply have to build the algorithm (usually represented by a logical circuit) computing $O$ from the algorithm computing the circuit oracle.

Since $O$ merely computes $B(v)$ from a given vertex, invokes the circuit oracle, and then performs a case distinction, it can clearly be built and queried in polynomial time in $n$.

\subparagraph*{Correctness}
To prove correctness of this reduction being promise preserving, we must show that 
every violation of \USO can be mapped back to a violation of \gls*{POMCP}\xspace
and every valid solution of \USO can be mapped back to a valid solution or a violation of \gls*{POMCP}\xspace.

\subparagraph{A solution of type \emph{(U1)}\xspace}

Let $\relax\ifmmode{v}\else{$v$}\fi\xspace \in V(Q_n)$ be a solution to the \USO instance, i.e., a sink. 

It might be that $v$ is a sink because $B(v)$ is not a basis, and thus $O(v)_i = -$ for all $i$. To map this back to a violation or solution of \gls*{POMCP}\xspace, we first check if the \gls*{POMCP}\xspace oracle returns that $B(v)$ is not a basis for the input $\f{C}\xspace(B(v), q)$. If so, we found a violation of type \emph{(MV2)}\xspace.
Otherwise, the fundamental circuit $\f{C}\xspace(B(v), q)$ is a solution to the \gls*{POMCP}\xspace instance: Since \relax\ifmmode{v}\else{$v$}\fi\xspace is a sink, there is no index at which the fundamental circuit is negative. All entries of $\f{C}\xspace(B(v), q)$ are positive and the complementarity condition is fulfilled by construction of $B(v)$. 

\subparagraph{A violation of type \emph{(UV1)}\xspace}

If a violation is found, we have two distinct vertices \relax\ifmmode{v}\else{$v$}\fi\xspace and \relax\ifmmode{w}\else{$w$}\fi\xspace with
$\forall i\in [k]:\; (\relax\ifmmode{v}\else{$v$}\fi\xspace_i = \relax\ifmmode{w}\else{$w$}\fi\xspace_i) \vee (O(\relax\ifmmode{v}\else{$v$}\fi\xspace)_i = O(\relax\ifmmode{w}\else{$w$}\fi\xspace)_i)$. We first again check whether $B(v)$ or $B(w)$ are bases, if not we map this violation to a violation of type \emph{(MV2)}\xspace.

Otherwise, we show that there are two distinct complementary circuits 
$\relax\ifmmode{X}\else{$X$}\fi\xspace, \relax\ifmmode{Y}\else{$Y$}\fi\xspace \in \relax\ifmmode{\mathcal{C}}\else{$\mathcal{C}$}\fi\xspace$ with $\relax\ifmmode{X}\else{$X$}\fi\xspace_q = \relax\ifmmode{Y}\else{$Y$}\fi\xspace_q = +$ and $\forall i \in [n] : X_{s_i}Y_{t_i}=X_{t_i}Y_{s_i}=0$ or $X_{s_i}=Y_{t_i}$ and $X_{t_i}=Y_{s_i}$, i.e., a violation of type \emph{(MV3)}\xspace.
We claim that the circuits
$\relax\ifmmode{X}\else{$X$}\fi\xspace := \f{C}\xspace(\relax\ifmmode{B}\else{$B$}\fi\xspace(\relax\ifmmode{v}\else{$v$}\fi\xspace), q)$ and $\relax\ifmmode{Y}\else{$Y$}\fi\xspace :=\f{C}\xspace(\relax\ifmmode{B}\else{$B$}\fi\xspace(\relax\ifmmode{w}\else{$w$}\fi\xspace), q)$ fulfill these conditions.

First, we need to show that $\relax\ifmmode{X}\else{$X$}\fi\xspace\neq \relax\ifmmode{Y}\else{$Y$}\fi\xspace$. If the two circuits were equal, they would have to be degenerate on all dimensions spanned by $v$ and $w$. Then by construction of $O$, $v$ and $w$ could not fail Szab{\'o}{}-Welzl (see \Cref{lem:completable}).

Next, we see that by definition $\f{C}\xspace(\relax\ifmmode{B}\else{$B$}\fi\xspace(\relax\ifmmode{v}\else{$v$}\fi\xspace), q)_q = +$ and $\f{C}\xspace(\relax\ifmmode{B}\else{$B$}\fi\xspace(\relax\ifmmode{w}\else{$w$}\fi\xspace), q)_q=+$ and both circuits are complementary.

Finally, we show that for each dimension $i$, either (i) $X_{s_i}Y_{t_i}=X_{t_i}Y_{s_i}=0$ or (ii) $X_{s_i}=Y_{t_i}$ and $X_{t_i}=Y_{s_i}$. For every dimension $i$ for which $v_i=w_i$ (w.l.o.g. both are $0$), both $\relax\ifmmode{X}\else{$X$}\fi\xspace_{t_i}=0$ and $\relax\ifmmode{Y}\else{$Y$}\fi\xspace_{t_i}=0$. Therefore, condition (i) holds. For a dimension $i$ for which $v_i\neq w_i$, if at least one of the $i$-edges incident to $v_i$ and $w_i$ is degenerate, we have $X_{s_i}=X_{t_i}=0$ (or $Y_{s_i}=Y_{t_i}=0$). Thus, condition (i) also holds in this case.
For a dimension $i$ in which both are non-degenerate, since $v$ and $w$ are a violation of type \emph{(UV1)}\xspace, $O(v)_i=O(w)_i$. By construction of $O$ it must hold that $X_{s_i}=Y_{t_i}$ and $X_{t_i}=Y_{s_i}$, i.e., condition (ii) holds.

Therefore, the circuits $\f{C}\xspace(\relax\ifmmode{B}\else{$B$}\fi\xspace(\relax\ifmmode{v}\else{$v$}\fi\xspace), q)$ and $\f{C}\xspace(\relax\ifmmode{B}\else{$B$}\fi\xspace(\relax\ifmmode{w}\else{$w$}\fi\xspace), q)$ form a violation of type \emph{(MV3)}\xspace.
\end{proof}

It follows that \gls*{POMCP}\xspace as defined in \Cref{def:TotalPOMCP} is in \UEOPL and its promise version is in \Class{PromiseUEOPL}\xspace.

\newpage
