1
$\begingroup$

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, 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Dec 20 '17 at 23:11
  • $\begingroup$ 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. $\endgroup$ – mak Dec 20 '17 at 23:18
  • $\begingroup$ Ok, self-answered this one now and will fix the other thread. Apologies for the unnecessary commotion. $\endgroup$ – mak Dec 20 '17 at 23:30
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.