Questions tagged [p-hardness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
69 views

Recursively presenting or even enumerating all P-hard languages

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\}$. ...
14
votes
4answers
694 views

P-complete problems on trees

This question is related to one of my previous questions, NP-hard problems on trees. I am looking for problems that are P-complete on trees.
10
votes
1answer
262 views

Density of P-complete languages

Suppose $L$ is a Boolean language, of finite strings over $\{0,1\}$. Let $L_n$ be the number of strings in $L$ with length $n$. For a function $d(n)$ from the positive integers to the positive real ...
39
votes
2answers
2k views

Are the problems PRIMES, FACTORING known to be P-hard?

Let PRIMES (a.k.a. primality testing) be the problem: Given a natural number $n$, is $n$ a prime number? Let FACTORING be the problem: Given natural numbers $n$, $m$ with $1 \leq m \leq n$, ...