Return to Question

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be an ordered finite set. Let $g:K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_{A_1}$ and $>_{A_2}$ such that:

$$k_1 >_{A_1} k_2 \text{ and } k'_1 >_{A_2} k'_2$$ If and only If $$g(k_1,k'_1) + g(k_2,k'_2) \ge g(k_1,k'_2) + g(k_2,k'_1)$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be a finite set. Let $g\colon K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_1$ and $>_2$ on $K$ such that $$s \, >_1 \,\, t \text{ and } x \, >_2 \,\, y$$ if and only if $$g(s,x) + g(t,y) \ge g(s,y) + g(t,x).$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be an ordered finite set. Let $g:K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_{A_1}$ and $>_{A_2}$ such that:

$$k_1 >_{A_1} k_2 \text{ and } k'_1 >_{A_2} k'_2$$ If and only If $$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be an ordered finite set. Let $g:K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_{A_1}$ and $>_{A_2}$ such that:

$$k_1 >_{A_1} k_2 \text{ and } k'_1 >_{A_2} k'_2$$ If and only If $$g(k_1,k'_1) + g(k_2,k'_2) \ge g(k_1,k'_2) + g(k_2,k'_1)$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (*) or verify that such orders A1,A2 doesn't exists.

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be an ordered finite set. Let $g:K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_{A_1}$ and $>_{A_2}$ such that:

$$k_1 >_{A_1} k_2 \text{ and } k'_1 >_{A_2} k'_2$$ If and only If $$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?