<p>Complexity theory implicitly makes use of "mild" orders all the time between complexity classes —  where there is a relation which is known in one direction, and <em>unknown</em> in another.</p>

<p>We might define a "hazy order" $\mathscr R$ to be a class of quasi-orders $\{R_j\}_{j \in J}$ together with a class of forbidden relations $F$. The set of quasi-orders is upward-closed "except where forbidden": that is, for quasi-orders $R, R'$ disjoint from $F$ such that $\forall j,k: j\mathbin{R}k \implies j\mathbin{R'}k$, we have $R\in\mathscr R \implies R'\in\mathscr R$.
Such a hazy order can be used to describe a single, definite quasi-order $R \subseteq A \times A$ by taking $\mathscr R = \{ R \}$ and $F = (A \times A) \smallsetminus R$.</p>

<p>For such a hazy order $(\mathscr R, F)$ on a set $A$, we write&ast;</p>

<ul>
<li>$j \leqslant_{\mathscr R} k$ if $\forall R \in \mathscr R: j \mathbin R k$, and</li>
<li>$j &lt;_{\mathscr R} k$ if furthermore $\forall R \in \mathscr R: \neg(k \mathbin R j)$.</li>
</ul>

<p>Thus there is room for fuzziness in relations, where $j \leqslant_{\mathscr R} k$, but neither $k \leqslant_{\mathscr R} j$ nor $j &lt;_{\mathscr R} k$ obtain. Because one cannot show  $k \leqslant_{\mathscr R} j$, one would tend to treat the relation as strict when describing upper and lower bounds, but because one cannot show $j &lt;_{\mathscr R} k$ one cannot <em>rely</em> on the inequivalence of $j$ and $k$. At the same time, the hazy order $\{ R \}$ given by any particular quasi-order $R$ satisfies $j &lt;_{\{R\}} k \iff (j \leqslant_{\{R\}} k) \mathbin{\&amp;} \neg(k \leqslant_{\{R\}} j)$, so describing it as a hazy order does not lead to any difference from the quasi-order $R$ itself. </p>

<p>Such a hazy order describes uncertain quasi-orders, such as our current state of knowledge of complexity classes: we know $\mathsf {P \subseteq NP}$, but our current formal knowledge is compatible with either $\mathsf {NP \subseteq P}$ or $\mathsf {NP \not\subseteq P}$ (whereas we do know that $\mathsf {EXP \not\subseteq P}$ for example). We act conventionally as though $\mathsf{P \subset NP \subset NP^{NP} \subset \cdots}$ but acknowledge that it is conceivable that this ordering is weak rather than strict as a quasi-order on complexity classes (or rather the labels of them — which we can take as representing their <em>intensional</em> identities, as opposed to their <em>extensions</em> as sets of problems).</p>

<p>A "mild" linear order such as the sort you describe (neither strict nor weak) could be one in which we consider some strict linear order $L \subset A \times A$, take the forbidden relations $F$ to be a proper subset of $(A \times A) \smallsetminus L$ (and in particular: one whose transitive closure as a relation does not contain the opposite relation $L^{\mathrm{op}}$ as a subset)&ast; and take $\mathscr R$ to be the upward closure of $\{L\}$ (i.e. under subset containment, among quasi-orders, subject to avoidance of $F$).</p>

<p>(&nbsp;&ast;&nbsp;<strong>N.B.</strong> These descriptions have been edited to correct errors involving the forbidden subset.)</p>

CC BY-SA 3.0
2014-04-25T09:25:23.740Z
Sorry but this doesn't make sense to me. Why did this answer get 1 upvote while my initial question got 3 downvotes? Should we reverse the signs to get 'meaningful' votes?
NisaiVloot
CC BY-SA 3.0
2014-04-25T09:54:14.750Z
@HeloLobo: Perhaps your question would have been better suited to MathOverflow or Mathematics.SE --- it provides no particular reason why the question might be of interest to theoretical computer science. (As mathematicians concerned with relationships, we like posets; and as practical mathematicians we like generalizations of things when those generalizations yield useful tools; but it is not obvious how your question would yield a tool appropriate to theoretical computer scientists.) But because I'm slightly pure-mathy, I decided to try to give an answer while showing how it relates to TCS.
Niel de Beaudrap
CC BY-SA 3.0
2014-04-25T08:37:26.603Z
2014-04-25T10:30:30.493Z
2014-04-25T10:30:30.493Z
Niel de Beaudrap
<p>This seems like a "big-list" and "broad interpretation" sort of question, so I'll throw one out there that is obvious (at least in retrospect) to TCS researchers.</p>

<p>Define an ordering $\preceq_f$ on languages where $A \preceq_f B$ if $A$ can be reduced to $B$ in time $O(f(n))$. (I am thinking of Karp or "many-one" reductions, but one could also think of Cook reductions, also consider space-bounded reductions, etc etc.)</p>

<p>With this notation, $A \preceq_f B$ tells us that $A$ is an easier problem than $B$, and $f$ controls the "strictness" of the relation. (Let's also extend the notation to classes of functions in the obvious way, so $A \preceq_{poly} B$ means there is a polynomial $f$ such that $A \preceq_f B$.)</p>

<p>Examples:</p>

<ul>
<li>$A \preceq_{poly} SAT$ for all languages $A \in NP$.</li>
<li>If $A$ and $B$ are both NP-complete, then we have $A \preceq_{poly} B$ and $B \preceq_{poly} A$.</li>
<li>If $P \neq NP$, then for any $A \in P$, $A \preceq_{poly} SAT$ yet $SAT \npreceq_{poly} A$.</li>
<li>If $A$ is decidable in time $O(f(n))$ and $B$ requires time $\Omega(g(n))$ with $f = o(g)$, then:
<ul>
<li>$A \preceq_g B$</li>
<li>$B \preceq_g A$</li>
<li>$A \preceq_f B$, but</li>
<li>$B \npreceq_f A$.</li>
</ul></li>
</ul>

<p>So we even have an ordering on our orderings: In the last example, $f$ gives a "stricter" relation than $g$.</p>

CC BY-SA 3.0
2014-04-25T12:36:37.037Z
Your reduction relation $\preceq_f$ is itself a [quasi-order, or preorder](http://en.wikipedia.org/wiki/Quasi-ordering) with pairs of "equivalent" elements for any $f \in \omega(1)$; it doesn't appear to address the question of a notion of a "mild" order (one which is neither a strict order, nor a quasi-order with distinct equivalent elements) or a "mild" anything else.
Niel de Beaudrap
CC BY-SA 3.0
2014-04-25T14:39:23.380Z
@NieldeBeaudrap, sure -- I don't know what "mild" is supposed to mean, so I don't know if this is a good answer. But I think it's an interesting family of orderings because there seem to be lots of possibilities. You could try to formalize notions like $A >_{0.8} B$ if a limiting $0.8$-fraction of strings can be decided for membership in $A$ faster than in $B$.
usul
CC BY-SA 3.0
2014-04-25T15:15:47.800Z
I think the problem is that even the author doesn't precisely know what they mean by "mild", and are just fishing around for something different than "weak" or "strict".
Niel de Beaudrap
CC BY-SA 3.0
2014-04-09T01:13:53.177Z
2014-04-09T01:13:53.177Z
usul
<p>It is commonly admitted that strict constraints can be relaxed through a 'fuzzy' or 'statistical' framework, as suggested by the paper 'Fuzzy topology and order', Antarctica J. Math, 4(1) (2007), pp. 147-165. However, I believe that the 'half-integrality' suggested above should be sufficient for your concern, without resorting to a continuous spectrum of values.</p>

CC BY-SA 3.0
2014-04-24T14:55:59.707Z
"Antarctica J. Math." as in, [this](http://www.domainsmoon.com/ajm.html)? **Warning:** do not click link unless wearing dark glasses.
David Richerby
CC BY-SA 3.0
2014-04-24T18:42:29.023Z
Judging by the contents, it seems one of the few 'serious' journals from this domainmoon website, despite the flashy and someone outdated presentation.
NisaiVloot
CC BY-SA 3.0
2014-04-23T21:59:00.093Z
2014-04-23T21:59:00.093Z
NisaiVloot
<p>This is more of a 'meta' question as I cannot give a precise formulation of my question. Consider for example the category of total quasi-orders: we can then distinguish between a 'strict' order (where no two elements are equivalent) and a 'weak order' (where some elements may belong to the same equivalence class). It doesn't possible to define an intermediate notion of 'mild order' in this setting, so do you have any suggestions for other structures allowing a natural notion of 'mildness' which is well-behaved?</p>

<p>I'd like to add a self-evident comment: in science the qualificative of 'mild' can be applied to certain notions, e.g. 'mild necessity', 'mild difficulty' or 'mild formalism' which describes well the questions that I'm asking. OTOH I guess we can't speak of a 'mildly correct' statement without resorting to statistics?</p>

CC BY-SA 3.0
2014-04-08T23:32:36.510Z
A note: you've asked a few questions now that seem relevant and interesting, but lack any reasonable motivation as to why you're asking them, and in particular why you're asking them on cstheory. Providing such motivation would be helpful.
Suresh Venkat
CC BY-SA 3.0
2014-04-08T23:37:16.080Z
Personally I have to be self-motivated as otherwise I would have given up research long ago :) But if you think that 'providing motivation' can increase the chance of getting an answer then I'll consider it.
NisaiVloot
CC BY-SA 3.0
2014-04-08T23:54:55.813Z
One more thing: I leave it to the reader's judgment to see which of my questions are interesting/enlightening. The basic motivation is to help increasing the interest span of the readers, as the website contains too many engineering/puzzles questions in my opinion - this is not what 'theory' should be about, right?
NisaiVloot
CC BY-SA 3.0
2014-04-09T00:35:03.987Z
I think the community decides what "theory" is :). My **personal** view is that your questions have a weaker connection to CSTheory and a stronger connection to basic math.
Suresh Venkat
CC BY-SA 3.0
2014-04-09T04:52:33.963Z
First, I agree with Suresh about motivation. Also, "deep question" vs. "puzzle" is an orthogonal issue to "theory of computing" vs "some other part of math". IMO your questions fall in the "puzzle" and "some other part of math" categories, which makes them an imperfect fit for this site. For this *particular* question, I think it's very broad and ill-defined, even for a "big picture" question.
Sasho Nikolov
CC BY-SA 3.0
2014-04-09T06:17:03.450Z
You should check [how to write a better question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question). Ask questions that you are actually thinking and seeking answer for, not questions out of idle curiosity. Keep in mind that this is not a discussion site but a Q&A site and it works better when questions are objectively answerable. If you want to ask a subjective question please make sure it follows [guidelines for good subjective questions](http://blog.stackoverflow.com/2010/09/good-subjective-bad-subjective/).
Kaveh
CC BY-SA 3.0
2014-04-09T06:32:26.463Z
@SashoNikolov: I'm not saying that my questions are 'deep' but that I try to make them 'interesting'. I agree though that they may fall too much on the algebra/discrete mathematics side to interest the general audience of the site. I apologize again for any formulation issues and I'll try to address them diligently.
NisaiVloot
CC BY-SA 3.0
2014-04-09T06:36:23.990Z
@SashoNikolov: Also, while the question is seemingly vague, by mentioning the strict quasi-orders it implicitly suggested some natural extension (i.e. considering a half-integral quasi-metric with values in $\{0,\frac{1}{2},1\}$). Probably this half-integrality notion is the right approach to get this 'mildness' property for free.
NisaiVloot
CC BY-SA 3.0
2014-04-11T06:24:42.273Z
It is not "seemingly vague", it is just vague: your question asks for "structures" that have the property of "mildness", where structures is entirely unrestricted and mildness is not defined and you have given one non-example of it.
Sasho Nikolov
CC BY-SA 3.0
2014-04-11T19:40:03.103Z
@SashoNikolov: Well, I was hoping that someone would come up with a precise 'definition' so that I don't have to do it myself... For instance, I suspect there should be a possible definition in terms of fractional homomorphisms, but it's still unclear.
NisaiVloot
CC BY-SA 3.0
2014-04-11T22:00:21.287Z
From this question, I am left with no clue what you are trying to define, even informally.
Sasho Nikolov
CC BY-SA 3.0
2014-04-11T23:23:26.363Z
@SashoNikolov: well, if the readers don't show any sign of good intentions I have no reasons to continue posting on this site, right? And I don't expect that mathematicians are more welcoming either....
NisaiVloot
CC BY-SA 3.0
2014-04-15T14:10:54.833Z
@HeloLobo They will be more welcoming because your questions will be on topic (but you'd still have to work harder to make them more precise). For evidence, why don't you sign into Mathoverflow and check your two migrated questions which have received IMO useful comments there: http://mathoverflow.net/q/163402/35733 and http://mathoverflow.net/q/163354/35733
Sasho Nikolov
CC BY-SA 3.0
2014-04-24T19:24:36.250Z
@HeloLobo: If you had included your example of fractional homomorphisms / half-integral quasi-metric, that would have *helped* give a sense of what you were looking for, but even then I still agree with SashoNikolov: I don't understand what you're looking for. Can you gave an *example* (rather than a non-example) of a definition of mildness that is between strict and weak, perhaps in a different setting?
Joshua Grochow
<big-picture>
What structures allow a notion of 'strictness', 'weakness' and 'mildness'?
NisaiVloot
# What structures allow a notion of 'strictness', 'weakness' and 'mildness'?

(Asked by: username_0 on 2014-04-08)

This is more of a 'meta' question as I cannot give a precise formulation of my question. Consider for example the category of total quasi-orders: we can then distinguish between a 'strict' order (where no two elements are equivalent) and a 'weak order' (where some elements may belong to the same equivalence class). It doesn't possible to define an intermediate notion of 'mild order' in this setting, so do you have any suggestions for other structures allowing a natural notion of 'mildness' which is well-behaved?

I'd like to add a self-evident comment: in science the qualificative of 'mild' can be applied to certain notions, e.g. 'mild necessity', 'mild difficulty' or 'mild formalism' which describes well the questions that I'm asking. OTOH I guess we can't speak of a 'mildly correct' statement without resorting to statistics?

**Tags:** big-picture

> **Comments:**
> **username_1**: A note: you've asked a few questions now that seem relevant and interesting, but lack any reasonable motivation as to why you're asking them, and in particular why you're asking them on cstheory. Providing such motivation would be helpful.  
> **username_0**: Personally I have to be self-motivated as otherwise I would have given up research long ago :) But if you think that 'providing motivation' can increase the chance of getting an answer then I'll consider it.  
> **username_0**: One more thing: I leave it to the reader's judgment to see which of my questions are interesting/enlightening. The basic motivation is to help increasing the interest span of the readers, as the website contains too many engineering/puzzles questions in my opinion - this is not what 'theory' should be about, right?  
> **username_1**: I think the community decides what "theory" is :). My **personal** view is that your questions have a weaker connection to CSTheory and a stronger connection to basic math.  
> **username_2**: First, I agree with Suresh about motivation. Also, "deep question" vs. "puzzle" is an orthogonal issue to "theory of computing" vs "some other part of math". IMO your questions fall in the "puzzle" and "some other part of math" categories, which makes them an imperfect fit for this site. For this *particular* question, I think it's very broad and ill-defined, even for a "big picture" question.  
> **username_3**: You should check [how to write a better question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question). Ask questions that you are actually thinking and seeking answer for, not questions out of idle curiosity. Keep in mind that this is not a discussion site but a Q&A site and it works better when questions are objectively answerable. If you want to ask a subjective question please make sure it follows [guidelines for good subjective questions](http://blog.stackoverflow.com/2010/09/good-subjective-bad-subjective/).  
> **username_0**: @SashoNikolov: I'm not saying that my questions are 'deep' but that I try to make them 'interesting'. I agree though that they may fall too much on the algebra/discrete mathematics side to interest the general audience of the site. I apologize again for any formulation issues and I'll try to address them diligently.  
> **username_0**: @SashoNikolov: Also, while the question is seemingly vague, by mentioning the strict quasi-orders it implicitly suggested some natural extension (i.e. considering a half-integral quasi-metric with values in $\{0,\frac{1}{2},1\}$). Probably this half-integrality notion is the right approach to get this 'mildness' property for free.  
> **username_2**: It is not "seemingly vague", it is just vague: your question asks for "structures" that have the property of "mildness", where structures is entirely unrestricted and mildness is not defined and you have given one non-example of it.  
> **username_0**: @SashoNikolov: Well, I was hoping that someone would come up with a precise 'definition' so that I don't have to do it myself... For instance, I suspect there should be a possible definition in terms of fractional homomorphisms, but it's still unclear.  
> **username_2**: From this question, I am left with no clue what you are trying to define, even informally.  
> **username_0**: @SashoNikolov: well, if the readers don't show any sign of good intentions I have no reasons to continue posting on this site, right? And I don't expect that mathematicians are more welcoming either....  
> **username_2**: @HeloLobo They will be more welcoming because your questions will be on topic (but you'd still have to work harder to make them more precise). For evidence, why don't you sign into Mathoverflow and check your two migrated questions which have received IMO useful comments there: http://mathoverflow.net/q/163402/35733 and http://mathoverflow.net/q/163354/35733  
> **username_4**: @HeloLobo: If you had included your example of fractional homomorphisms / half-integral quasi-metric, that would have *helped* give a sense of what you were looking for, but even then I still agree with SashoNikolov: I don't understand what you're looking for. Can you gave an *example* (rather than a non-example) of a definition of mildness that is between strict and weak, perhaps in a different setting?  

---

## 3 answers

### Answer by username_5 on 2014-04-25. Score: 3

Complexity theory implicitly makes use of "mild" orders all the time between complexity classes — where there is a relation which is known in one direction, and *unknown* in another.

We might define a "hazy order" $\mathscr R$ to be a class of quasi-orders $\{R\_j\}\_{j \in J}$ together with a class of forbidden relations $F$. The set of quasi-orders is upward-closed "except where forbidden": that is, for quasi-orders $R, R'$ disjoint from $F$ such that $\forall j,k: j\mathbin{R}k \implies j\mathbin{R'}k$, we have $R\in\mathscr R \implies R'\in\mathscr R$.
Such a hazy order can be used to describe a single, definite quasi-order $R \subseteq A \times A$ by taking $\mathscr R = \{ R \}$ and $F = (A \times A) \smallsetminus R$.

For such a hazy order $(\mathscr R, F)$ on a set $A$, we write\*

* $j \leqslant\_{\mathscr R} k$ if $\forall R \in \mathscr R: j \mathbin R k$, and
* $j <\_{\mathscr R} k$ if furthermore $\forall R \in \mathscr R: \neg(k \mathbin R j)$.

Thus there is room for fuzziness in relations, where $j \leqslant\_{\mathscr R} k$, but neither $k \leqslant\_{\mathscr R} j$ nor $j <\_{\mathscr R} k$ obtain. Because one cannot show $k \leqslant\_{\mathscr R} j$, one would tend to treat the relation as strict when describing upper and lower bounds, but because one cannot show $j <\_{\mathscr R} k$ one cannot *rely* on the inequivalence of $j$ and $k$. At the same time, the hazy order $\{ R \}$ given by any particular quasi-order $R$ satisfies $j <\_{\{R\}} k \iff (j \leqslant\_{\{R\}} k) \mathbin{\&} \neg(k \leqslant\_{\{R\}} j)$, so describing it as a hazy order does not lead to any difference from the quasi-order $R$ itself.

Such a hazy order describes uncertain quasi-orders, such as our current state of knowledge of complexity classes: we know $\mathsf {P \subseteq NP}$, but our current formal knowledge is compatible with either $\mathsf {NP \subseteq P}$ or $\mathsf {NP \not\subseteq P}$ (whereas we do know that $\mathsf {EXP \not\subseteq P}$ for example). We act conventionally as though $\mathsf{P \subset NP \subset NP^{NP} \subset \cdots}$ but acknowledge that it is conceivable that this ordering is weak rather than strict as a quasi-order on complexity classes (or rather the labels of them — which we can take as representing their *intensional* identities, as opposed to their *extensions* as sets of problems).

A "mild" linear order such as the sort you describe (neither strict nor weak) could be one in which we consider some strict linear order $L \subset A \times A$, take the forbidden relations $F$ to be a proper subset of $(A \times A) \smallsetminus L$ (and in particular: one whose transitive closure as a relation does not contain the opposite relation $L^{\mathrm{op}}$ as a subset)\* and take $\mathscr R$ to be the upward closure of $\{L\}$ (i.e. under subset containment, among quasi-orders, subject to avoidance of $F$).

( \* **N.B.** These descriptions have been edited to correct errors involving the forbidden subset.)

> **Comments:**
> **username_0**: Sorry but this doesn't make sense to me. Why did this answer get 1 upvote while my initial question got 3 downvotes? Should we reverse the signs to get 'meaningful' votes?  
> **username_5**: @HeloLobo: Perhaps your question would have been better suited to MathOverflow or Mathematics.SE --- it provides no particular reason why the question might be of interest to theoretical computer science. (As mathematicians concerned with relationships, we like posets; and as practical mathematicians we like generalizations of things when those generalizations yield useful tools; but it is not obvious how your question would yield a tool appropriate to theoretical computer scientists.) But because I'm slightly pure-mathy, I decided to try to give an answer while showing how it relates to TCS.  

---

### Answer by username_6 on 2014-04-09. Score: 1

This seems like a "big-list" and "broad interpretation" sort of question, so I'll throw one out there that is obvious (at least in retrospect) to TCS researchers.

Define an ordering $\preceq\_f$ on languages where $A \preceq\_f B$ if $A$ can be reduced to $B$ in time $O(f(n))$. (I am thinking of Karp or "many-one" reductions, but one could also think of Cook reductions, also consider space-bounded reductions, etc etc.)

With this notation, $A \preceq\_f B$ tells us that $A$ is an easier problem than $B$, and $f$ controls the "strictness" of the relation. (Let's also extend the notation to classes of functions in the obvious way, so $A \preceq\_{poly} B$ means there is a polynomial $f$ such that $A \preceq\_f B$.)

Examples:

* $A \preceq\_{poly} SAT$ for all languages $A \in NP$.
* If $A$ and $B$ are both NP-complete, then we have $A \preceq\_{poly} B$ and $B \preceq\_{poly} A$.
* If $P \neq NP$, then for any $A \in P$, $A \preceq\_{poly} SAT$ yet $SAT \npreceq\_{poly} A$.
* If $A$ is decidable in time $O(f(n))$ and $B$ requires time $\Omega(g(n))$ with $f = o(g)$, then:
  + $A \preceq\_g B$
  + $B \preceq\_g A$
  + $A \preceq\_f B$, but
  + $B \npreceq\_f A$.

So we even have an ordering on our orderings: In the last example, $f$ gives a "stricter" relation than $g$.

> **Comments:**
> **username_5**: Your reduction relation $\preceq_f$ is itself a [quasi-order, or preorder](http://en.wikipedia.org/wiki/Quasi-ordering) with pairs of "equivalent" elements for any $f \in \omega(1)$; it doesn't appear to address the question of a notion of a "mild" order (one which is neither a strict order, nor a quasi-order with distinct equivalent elements) or a "mild" anything else.  
> **username_6**: @NieldeBeaudrap, sure -- I don't know what "mild" is supposed to mean, so I don't know if this is a good answer. But I think it's an interesting family of orderings because there seem to be lots of possibilities. You could try to formalize notions like $A >_{0.8} B$ if a limiting $0.8$-fraction of strings can be decided for membership in $A$ faster than in $B$.  
> **username_5**: I think the problem is that even the author doesn't precisely know what they mean by "mild", and are just fishing around for something different than "weak" or "strict".  

---

### Answer by username_0 on 2014-04-23. Score: -2

It is commonly admitted that strict constraints can be relaxed through a 'fuzzy' or 'statistical' framework, as suggested by the paper 'Fuzzy topology and order', Antarctica J. Math, 4(1) (2007), pp. 147-165. However, I believe that the 'half-integrality' suggested above should be sufficient for your concern, without resorting to a continuous spectrum of values.

> **Comments:**
> **username_7**: "Antarctica J. Math." as in, [this](http://www.domainsmoon.com/ajm.html)? **Warning:** do not click link unless wearing dark glasses.  
> **username_0**: Judging by the contents, it seems one of the few 'serious' journals from this domainmoon website, despite the flashy and someone outdated presentation.  

---

