<p>After some further thought, partly triggered by writing a long question, it seems clear that the set of P-hard languages is not countable, and therefore not recursively presentable either.</p>

<p>To see why, consider languages $L$ that satisfy $w\in 2SAT$ iff $ww\in L$. 2SAT can be log-space reduced to any such language by definition. However, there are countably many words that do not have the form $ww$, and the languages might differ on their membership status. Hence we obtain uncountably many P-hard languages of this form.</p>

<p>Moreover, it does not seem possible to recursively present all decidable P-hard languages either, since there is no effective enumeration of all Turing machines that are guaranteed to halt (this seems to be the minimal requirement for applying Schöning's construction).</p>

CC BY-SA 3.0
2017-12-20T23:27:29.403Z
2017-12-20T23:27:29.403Z
mak
<p>A class of languages $C$ is <em>recursively presentable</em> if there is an effective enumeration of Turing machines $\mathcal{M}_1,\mathcal{M}_2,\ldots$ such that $C=\{L(\mathcal{M}_i)\mid i=1,2,\ldots\}$. Uwe Schöning considers this notion in his elegant generalisation of Ladner's theorem ("A Uniform Approach to Obtain Diagonal Sets in Complexity Classes", Theor. Comp. Sci. 18, 1982).</p>

<p>In <a href="https://cstheory.stackexchange.com/a/8046/17577">a previous answer on this site</a>, Ryan Williams argues that the set of all P-hard languages can be recursively presented "similar to how Schoening does it for the NP-hard sets". I would like to know how this works, since I cannot find this in the paper. Schöning works with Turing reductions and shows that the NP-complete sets are recursively presentable. We can adapt his argument to NP-complete sets under polynomial many-one reductions as follows:</p>

<ol>
<li>Take an enumeration $(\mathcal{M}_i,\mathcal{R}_i)_{i\geq 1}$ of pairs of polynomially time-bounded non-deterministic Turing machines $\mathcal{M}_i$ and polynomial reductions $\mathcal{R}_i$ (we can enumerate polytime machines and reductions by enumerating all machines and polynomials, and augmenting them with a polytime "stop clock" that enforces timely halting).</li>
<li>For each pair of a machine $\mathcal{M}_i$ and reduction $\mathcal{R}_i$, the let $\mathcal{M}'_i$ denote a machine that does the following on input word $w$:

<ul>
<li>For all input words $v$ with $|v|&lt;|w|$, test whether $\mathrm{SAT}(v)=\mathcal{M}_i(\mathcal{R}_i(v))$, i.e., whether $\mathcal{R}_i$ reduces $\mathrm{SAT}$ to $L(\mathcal{M}_i)$ on these instances.</li>
<li>If yes, accept iff $\mathcal{M}_i$ accepts $w$</li>
<li>If no, accept iff $w\in\mathrm{SAT}$</li>
</ul></li>
</ol>

<p>The required enumeration is $\mathcal{M}'_1,\mathcal{M}'_2,\ldots$, since each of those either decides $\mathrm{SAT}$ (up to finitely many cases) or some other language in NP to which $\mathrm{SAT}$ can truly be reduced.</p>

<p>I do not see how to apply this idea to recursively present all P-hard languages. One could readily recursively present, e.g., all <em>P-hard languages in ExpTime</em> (which would suffice as an answer in the other thread), but I don't see why the P-hard languages in general (including undecidable ones) should even be countable.</p>

CC BY-SA 3.0
2017-12-20T23:11:33.213Z
In Ryan's answer, it's enough to enumerate P-hard languages in EXP, which you already see how to do. If you want all (computable) P-hard languages, this method won't show that the set of P-hard computable languages is recursively presentable, since I'm pretty sure the set of (total) computable languages is not recursively presentable.
Joshua Grochow
CC BY-SA 3.0
2017-12-20T23:18:29.047Z
Yes, the set of total recursive functions is not recursively enumerable. I also agree on the other part (as mentioned in my post). The fact that P-hard languages are not countable also seems to be quite easy t show.
mak
CC BY-SA 3.0
2017-12-20T23:30:24.137Z
Ok, self-answered this one now and will fix the other thread. Apologies for the unnecessary commotion.
mak
<cc.complexity-theory><complexity-classes><p-hardness>
Recursively presenting or even enumerating all P-hard languages
mak
# Recursively presenting or even enumerating all P-hard languages

(Asked by: username_0 on 2017-12-20)

A class of languages $C$ is *recursively presentable* if there is an effective enumeration of Turing machines $\mathcal{M}\_1,\mathcal{M}\_2,\ldots$ such that $C=\{L(\mathcal{M}\_i)\mid i=1,2,\ldots\}$. Uwe Schöning considers this notion in his elegant generalisation of Ladner's theorem ("A Uniform Approach to Obtain Diagonal Sets in Complexity Classes", Theor. Comp. Sci. 18, 1982).

In [a previous answer on this site](https://cstheory.stackexchange.com/a/8046/17577), Ryan Williams argues that the set of all P-hard languages can be recursively presented "similar to how Schoening does it for the NP-hard sets". I would like to know how this works, since I cannot find this in the paper. Schöning works with Turing reductions and shows that the NP-complete sets are recursively presentable. We can adapt his argument to NP-complete sets under polynomial many-one reductions as follows:

1. Take an enumeration $(\mathcal{M}\_i,\mathcal{R}\_i)\_{i\geq 1}$ of pairs of polynomially time-bounded non-deterministic Turing machines $\mathcal{M}\_i$ and polynomial reductions $\mathcal{R}\_i$ (we can enumerate polytime machines and reductions by enumerating all machines and polynomials, and augmenting them with a polytime "stop clock" that enforces timely halting).
2. For each pair of a machine $\mathcal{M}\_i$ and reduction $\mathcal{R}\_i$, the let $\mathcal{M}'\_i$ denote a machine that does the following on input word $w$:
   * For all input words $v$ with $|v|<|w|$, test whether $\mathrm{SAT}(v)=\mathcal{M}\_i(\mathcal{R}\_i(v))$, i.e., whether $\mathcal{R}\_i$ reduces $\mathrm{SAT}$ to $L(\mathcal{M}\_i)$ on these instances.
   * If yes, accept iff $\mathcal{M}\_i$ accepts $w$
   * If no, accept iff $w\in\mathrm{SAT}$

The required enumeration is $\mathcal{M}'\_1,\mathcal{M}'\_2,\ldots$, since each of those either decides $\mathrm{SAT}$ (up to finitely many cases) or some other language in NP to which $\mathrm{SAT}$ can truly be reduced.

I do not see how to apply this idea to recursively present all P-hard languages. One could readily recursively present, e.g., all *P-hard languages in ExpTime* (which would suffice as an answer in the other thread), but I don't see why the P-hard languages in general (including undecidable ones) should even be countable.

**Tags:** cc.complexity-theory, complexity-classes, p-hardness

> **Comments:**
> **username_1**: In Ryan's answer, it's enough to enumerate P-hard languages in EXP, which you already see how to do. If you want all (computable) P-hard languages, this method won't show that the set of P-hard computable languages is recursively presentable, since I'm pretty sure the set of (total) computable languages is not recursively presentable.  
> **username_0**: Yes, the set of total recursive functions is not recursively enumerable. I also agree on the other part (as mentioned in my post). The fact that P-hard languages are not countable also seems to be quite easy t show.  
> **username_0**: Ok, self-answered this one now and will fix the other thread. Apologies for the unnecessary commotion.  

---

## 1 answers

### Answer by username_0 on 2017-12-20. Score: 4 | Accepted answer

After some further thought, partly triggered by writing a long question, it seems clear that the set of P-hard languages is not countable, and therefore not recursively presentable either.

To see why, consider languages $L$ that satisfy $w\in 2SAT$ iff $ww\in L$. 2SAT can be log-space reduced to any such language by definition. However, there are countably many words that do not have the form $ww$, and the languages might differ on their membership status. Hence we obtain uncountably many P-hard languages of this form.

Moreover, it does not seem possible to recursively present all decidable P-hard languages either, since there is no effective enumeration of all Turing machines that are guaranteed to halt (this seems to be the minimal requirement for applying Schöning's construction).


---

